Référence pour l'algorithme de test d'acyclicité de graphe mixte?

16

Un graphique mixte est un graphique qui peut avoir à la fois des bords orientés et non orientés. Son graphe non orienté sous-jacent est obtenu en oubliant les orientations des arêtes dirigées, et dans l'autre sens, une orientation d'un graphe mixte est obtenue en affectant une direction à chaque arête non orientée. Un ensemble d'arêtes forme un cycle dans un graphique mixte s'il peut être orienté pour former un cycle dirigé. Un graphique mixte est acyclique si et seulement s'il n'a pas de cycles.

Tout cela est standard et de nombreux articles publiés mentionnent des graphiques mixtes acycliques. Il faut donc connaître l'algorithme suivant pour tester l'acyclicité des graphes mixtes:

Répétez les étapes suivantes:

  • Supprimez tout sommet sans arêtes dirigées entrantes et sans arêtes non dirigées incidentes, car il ne peut faire partie d'aucun cycle.
  • Si un sommet n'a pas d'arêtes dirigées entrantes mais qu'il a exactement une arête non orientée incidente, tout cycle utilisant l'arête non dirigée doit arriver sur cette arête. Remplacez le bord non dirigé par un bord dirigé entrant.

Arrêtez lorsque plus aucune étape ne peut être effectuée. Si le résultat est un graphe vide, alors le graphe d'origine doit nécessairement avoir été acyclique. Sinon, à partir de n'importe quel sommet restant, on peut revenir en arrière dans le graphique, à chaque étape suivant en arrière à travers un bord entrant ou en suivant un bord non orienté qui n'est pas celui utilisé pour atteindre le sommet actuel, jusqu'à voir un sommet répété. La séquence d'arêtes suivie entre la première et la deuxième répétition de ce sommet (dans l'ordre inverse) forme un cycle dans le graphique mixte.

L'article de Wikipedia sur les graphiques mixtes mentionne les graphiques mixtes acycliques mais ne mentionne pas comment les tester, donc je voudrais y ajouter quelque chose à propos de cet algorithme, mais pour cela j'ai besoin d'une référence publiée. Quelqu'un peut-il me dire où il (ou tout autre algorithme pour tester l'acyclicité) apparaît dans la littérature?

ds.algorithms reference-request graph-theory graph-algorithms directed-acyclic-graph David Eppstein
la source
que se passe-t-il lorsqu'un sommet a deux arêtes incidentes non dirigées et aucune autre arête? Par exemple dans un triangle non orienté. Je veux dire que les règles ci-dessus couvrent ce cas?
Mateus de Oliveira Oliveira
Vous ne pouvez rien faire contre un tel sommet tant qu'un autre sommet n'applique pas la règle qui oriente l'une des arêtes. Si vous êtes coincé dans une situation où de tels sommets existent et que vous ne pouvez plus appliquer de règles, votre graphique contient un cycle.
David Eppstein
Il serait peut-être plus clair de considérer ce qui se passe dans le cas où votre graphique n'est pas dirigé. Une façon de tester s'il s'agit d'une forêt consiste à supprimer les feuilles (sommets de degré un) et les sommets isolés jusqu'à ce que vous obteniez un graphique vide (c'est une forêt) ou un noyau à 2 noyaux non trivial (un sous-graphique dans lequel tous les sommets ont un degré ≥ 2, qui contient nécessairement un cycle). L'algorithme de graphe mixte dégénère en ceci dans le cas non orienté (sauf qu'il oriente les feuilles plutôt que de les supprimer immédiatement), tout comme il dégénère en un algorithme de tri topologique standard dans le cas dirigé.
David Eppstein
Je ne sais pas si vous avez vu: il y a un post sur cs.stackexchange qui pose une question similaire ref . Le répondeur donne un algorithme pour trouver un cycle dans un graphique mixte en orientant les bords non orientés, en rejetant le graphique s'il n'existe pas. Il y a aussi du papier (s) sur déterminer si un graphique mixte est fortement orientable ref mais étrangement, n'a pas pu trouver quoi que ce soit réellement trouver les composants connectés dans les graphiques mixtes.
Quanquan Liu
Merci - non, je n'avais pas vu ça. La question "trouver une orientation pour que le graphique contienne un cycle dirigé" est certainement la même, et l'algorithme dans la réponse semble correct. Mais contrairement à celui que je décris, ce n'est pas du temps linéaire.
David Eppstein

Réponses:

1

Trouver des cycles mixtes dans un graphe mixte équivaut à trouver des cycles dirigés élémentaires (de longueur> = 3) dans le graphe dirigé correspondant. Le graphique dirigé correspondant est obtenu à partir du graphique mixte en remplaçant chaque bord non dirigé par deux bords dirigés pointant dans des directions opposées. Preuve: (1) Chaque cycle élémentaire dirigé (de longueur> = 3) dans le digraphe correspond directement à un cycle mixte dans le graphique mixte. (2) Chaque cycle mixte dans le graphique mixte contient un cycle mixte élémentaire de longueur> = 3, et chaque cycle de ce type correspond directement à un cycle élémentaire dirigé (de longueur> = 3) dans le graphique dirigé. (1) et (2) prouvent ensemble les deux directions de la déclaration, qed. Nous recherchons donc des références pour calculer (tous?) Des cycles élémentaires (de longueur> = 3) dans un graphe orienté.

Les commentaires indiquent que cs.stackexchange contient des réponses à cette question, mais il n'est pas clair comment organiser les résultats en une réponse concise. Ce billet de blog semble résumer joliment les (les plus?) Références importantes:

Algorithme de R. Tarjan

Le premier algorithme que j'ai inclus a été publié par R. Tarjan en 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

Algorithme de DB Johnson

L'algorithme de DB Johnson de 1975 améliore l'algorithme de Tarjan par sa complexité.

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

Dans le pire des cas, l'algorithme de Tarjan a une complexité temporelle de O (n⋅e (c + 1)) tandis que l'algorithme de Johnson parvient censément à rester dans O ((n + e) ​​(c + 1)) où n est le nombre de sommets, e est le nombre d'arêtes et c est le nombre de cycles dans le graphique.

Algorithme de KA Hawick et HA James

L'algorithme de KA Hawick et HA James de 2008 améliore encore l'algorithme de Johnson et supprime ses limites.

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

Contrairement à l'algorithme de Johnson, l'algorithme de KA Hawick et HA James est capable de gérer des graphiques contenant des arêtes qui commencent et se terminent au même sommet ainsi que plusieurs arêtes reliant les deux mêmes sommets.

Le test d'acyclicité lui-même semble être facile: calculez les composants fortement connectés du graphique. Tout cycle (élémentaire) est entièrement contenu dans un composant fortement connecté. Un composant fortement connecté contient un cycle élémentaire si ce n'est pas un arbre non orienté.

L'algorithme proposé par David Eppstein calcule en outre un cycle élémentaire comme preuve, et les algorithmes ci-dessus énumèrent tous les cycles élémentaires. Tout sommet ou bord non contenu dans un cycle élémentaire pourrait être supprimé comme étape de prétraitement pour améliorer la vitesse des algorithmes ci-dessus. L'algorithme de David Eppstein pourrait être utilisé à cette fin, mais même s'il n'est utilisé que sur les composants fortement connectés, il ne supprimera pas tous les sommets ou arêtes possibles qui peuvent être supprimés. Mais même s'il pourrait être étendu pour ce faire (le calcul de l' arbre de coupe en bloc permet au moins de supprimer tous les sommets possibles qui peuvent être supprimés), il n'est pas clair si cela améliorerait vraiment la vitesse des algorithmes ci-dessus.

Thomas Klimpel
la source
L'une de ces références mentionne-t-elle même des graphiques mixtes? Je sais comment trouver des cycles dans des graphiques dirigés. Ma question portait sur l'extension de ces algorithmes à des graphiques mixtes.
David Eppstein
@DavidEppstein Trouver des cycles mixtes dans un graphe mixte équivaut à trouver des cycles élémentaires (de longueur> = 3) dans le graphe orienté correspondant. Trouver une référence pour cette déclaration peut être difficile, mais prouver cette déclaration est simple. J'ai maintenant ajouté la déclaration et sa preuve à la réponse. (Ajout également d'une remarque sans preuve que le calcul de l' arbre de coupe en bloc permet de supprimer tous les sommets possibles qui peuvent être supprimés sans affecter les cycles élémentaires.)
Thomas Klimpel
D'accord, mais ils ne sont pas non plus linéaires.
David Eppstein
@DavidEppstein Le test d'acyclicité lui-même est effectué en temps linéaire. Mais vous avez raison, le temps dont l'un de ces algorithmes a besoin pour trouver le premier circuit élémentaire (de longueur> = 3) n'est pas linéaire (dans le pire des cas). Pire, la plupart des implémentations disponibles de l'algorithme de Johnson semblent utiliser plus de O ((n + e) ​​(c + 1)) temps, lorsqu'elles sont appliquées à un seul cercle dirigé (avec n sommets, e = n bords et c = 1 élémentaire cycles). Pourtant, cela devait être une réponse correcte, car l'article de Johnson semble être la référence la plus citée pour "trouver des circuits élémentaires".
Thomas Klimpel