Referência para o algoritmo de teste de aciclicidade de grafos mistos?

16

Um gráfico misto é um gráfico que pode ter bordas direcionadas e não direcionadas. Seu gráfico não direcionado subjacente é obtido esquecendo as orientações das arestas direcionadas e, na outra direção, uma orientação de um gráfico misto é obtida atribuindo uma direção a cada aresta não direcionada. Um conjunto de arestas forma um ciclo em um gráfico misto, se puder ser orientado para formar um ciclo direcionado. Um gráfico misto é acíclico se e somente se não tiver ciclos.

Isso tudo é padrão e há muitos artigos publicados mencionando gráficos mistos acíclicos. Portanto, o seguinte algoritmo para testar a aciclicidade de gráficos mistos deve ser conhecido:

Repita as seguintes etapas:

  • Remova qualquer vértice que não tenha arestas direcionadas recebidas nem arestas não direcionadas incidentes, pois não pode fazer parte de nenhum ciclo.
  • Se qualquer vértice não tiver arestas direcionadas recebidas, mas tiver exatamente uma aresta não direcionada incidente, qualquer ciclo usando a aresta não direcionada deverá entrar nessa aresta. Substitua a borda não direcionada por uma borda direcionada de entrada.

Pare quando não for possível executar mais etapas. Se o resultado for um gráfico vazio, o gráfico original deve necessariamente ter sido acíclico. Caso contrário, a partir de qualquer vértice restante, é possível voltar ao gráfico, em cada etapa seguindo para trás por uma aresta de entrada ou seguindo uma aresta não direcionada que não é a usada para alcançar o vértice atual, até ver um vértice repetido. A sequência de arestas seguida entre a primeira e a segunda repetição desse vértice (na ordem inversa) forma um ciclo no gráfico misto.

O artigo da Wikipedia sobre gráficos mistos menciona gráficos mistos acíclicos, mas não menciona como testá-los, então eu gostaria de acrescentar algo sobre esse algoritmo, mas para isso eu preciso de uma referência publicada. Alguém pode me dizer onde ele (ou qualquer outro algoritmo para testar a aciclicidade) aparece na literatura?

ds.algorithms reference-request graph-theory graph-algorithms directed-acyclic-graph David Eppstein
fonte
o que acontece quando um vértice tem duas arestas não direcionadas incidentes e nenhuma outra aresta? Por exemplo, em um triângulo não direcionado. Quero dizer, as regras acima cobrem este caso?
Mateus de Oliveira Oliveira
Você não pode fazer nada sobre esse vértice até que um vértice diferente aplique a regra que orienta uma das arestas. Se você ficar preso a uma situação em que esses vértices existem e não puder aplicar mais regras, seu gráfico conterá um ciclo.
David Eppstein
Talvez seja mais claro considerar o que acontece no caso de seu gráfico não ser direcionado. Uma maneira de testar se é uma floresta é remover folhas (vértices de grau um) e vértices isolados até você obter um gráfico vazio (é uma floresta) ou um núcleo central não trivial (um subgrafo no qual todos os vértices têm grau ≥ 2, que necessariamente contém um ciclo). O algoritmo de gráfico misto degenera para isso no caso não direcionado (exceto que orienta as folhas em vez de removê-las imediatamente), assim como degenera para um algoritmo de classificação topológica padrão no caso direcionado.
David Eppstein
Não tenho certeza se você viu: há uma postagem no cs.stackexchange que faz uma pergunta semelhante ref . O respondente fornece um algoritmo para encontrar um ciclo em um gráfico misto, orientando as bordas não direcionadas, rejeitando o gráfico se ele não existir. Há também artigo (s) sobre como determinar se um gráfico misto é uma referência fortemente orientável, mas estranhamente, não foi possível encontrar nada sobre como encontrar componentes conectados em gráficos mistos.
Quanquan Liu
Obrigado - não, eu não tinha visto isso. A pergunta "encontre uma orientação para fazer o gráfico conter um ciclo direcionado" é definitivamente a mesma e o algoritmo na resposta parece correto. Mas, diferentemente do que eu descrevo, não é um tempo linear.
David Eppstein

Respostas:

1

Encontrar ciclos mistos em um gráfico misto é equivalente a encontrar ciclos direcionados elementares (de comprimento> = 3) no gráfico direcionado correspondente. O gráfico direcionado correspondente é obtido do gráfico misto, substituindo cada aresta não direcionada por duas arestas direcionadas apontando em direções opostas. Prova: (1) Cada ciclo direcionado elementar (de comprimento> = 3) no dígrafo corresponde diretamente a um ciclo misto no gráfico misto. (2) Cada ciclo misto no gráfico misto contém um ciclo misto elementar de comprimento> = 3, e cada um desses ciclos corresponde diretamente a um ciclo direcionado elementar (de comprimento> = 3) no gráfico direcionado. (1) e (2) juntos provam ambas as direções da afirmação, qed. Portanto, estamos procurando referências sobre como calcular (todos?) Ciclos elementares (de comprimento> = 3) em um gráfico direcionado.

Os comentários indicam que o cs.stackexchange contém algumas respostas para essa pergunta, mas não está claro como organizar os resultados em uma resposta concisa. Esta postagem do blog parece resumir bem as (mais?) Referências importantes:

Algoritmo por R. Tarjan

O algoritmo mais antigo que incluí foi publicado por R. Tarjan em 1973.

Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

Algoritmo por DB Johnson

O algoritmo de DB Johnson de 1975 aprimora o algoritmo de Tarjan por sua complexidade.

Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

No pior dos casos, o algoritmo de Tarjan tem uma complexidade de tempo de O (n⋅e (c + 1)), enquanto o algoritmo de Johnson supostamente consegue permanecer em O ((n + e) ​​(c + 1)) onde n é o número de vértices, e é o número de arestas ec é o número de ciclos no gráfico.

Algoritmo de KA Hawick e HA James

O algoritmo de KA Hawick e HA James de 2008 melhora ainda mais o algoritmo de Johnson e elimina suas limitações.

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf

Em contraste com o algoritmo de Johnson, o algoritmo de KA Hawick e HA James é capaz de lidar com gráficos contendo arestas que começam e terminam no mesmo vértice, além de várias arestas conectando os mesmos dois vértices.

O teste de aciclicidade parece ser fácil: calcule os componentes fortemente conectados do gráfico. Qualquer ciclo (elementar) está completamente contido em um componente fortemente conectado. Um componente fortemente conectado contém um ciclo elementar se não for uma árvore não direcionada.

O algoritmo proposto por David Eppstein calcula adicionalmente um ciclo elementar como evidência, e os algoritmos acima enumeram todos os ciclos elementares. Qualquer vértice ou aresta não contida em um ciclo elementar pode ser excluída como uma etapa de pré-processamento para melhorar a velocidade dos algoritmos acima. O algoritmo de David Eppstein pode ser usado para esse fim, mas mesmo se usado apenas em componentes fortemente conectados, ele não excluirá todos os vértices ou arestas possíveis que possam ser excluídos. Mas mesmo que pudesse ser estendido para isso (calcular a árvore cortada em bloco pelo menos permite excluir todos os vértices possíveis que podem ser excluídos), não está claro se isso realmente melhoraria a velocidade dos algoritmos acima.

Thomas Klimpel
fonte
Alguma dessas referências menciona gráficos mistos? Eu sei como encontrar ciclos em gráficos direcionados. Minha pergunta era sobre extensões desses algoritmos para gráficos mistos.
David Eppstein
@DavidEppstein Encontrar ciclos mistos em um gráfico misto é equivalente a encontrar ciclos elementares (de comprimento> = 3) no gráfico direcionado correspondente. Encontrar uma referência para essa afirmação pode ser um desafio, mas provar que ela é simples. Eu agora adicionei a declaração e sua prova à resposta. (Também acrescentou uma observação sem prova de que o cálculo da árvore bloco de corte permite eliminar todos os vértices possível que pode ser excluído sem afetar os ciclos elementares.)
Thomas Klimpel
Ok, mas eles também ainda não são lineares.
David Eppstein
@DavidEppstein O teste de aciclicidade é realizado em tempo linear. Mas você está certo, o tempo em que qualquer um desses algoritmos precisa encontrar o primeiro circuito elementar (de comprimento> = 3) não é linear (no pior caso). Pior, a maioria das implementações disponíveis do algoritmo de Johnson parece usar mais do que tempo O ((n + e) ​​(c + 1)), quando aplicada a um único círculo direcionado (com n vértices, e = n arestas ec = 1 elementar ciclos). Ainda assim, essa foi uma resposta correta, porque o artigo de Johnson parece ser a referência mais citada para "encontrar circuitos elementares".
Thomas Klimpel 01/09/2015