Referenz für den Algorithmus zum Testen der Azyklizität gemischter Graphen?

16

Ein gemischtes Diagramm ist ein Diagramm, das sowohl gerichtete als auch ungerichtete Kanten haben kann. Das zugrunde liegende ungerichtete Diagramm wird erhalten, indem die Ausrichtungen der gerichteten Kanten vergessen werden, und in der anderen Richtung wird eine Ausrichtung eines gemischten Diagramms erhalten, indem jeder ungerichteten Kante eine Richtung zugewiesen wird. Ein Satz von Kanten bildet einen Zyklus in einem gemischten Diagramm, wenn er so ausgerichtet werden kann, dass er einen gerichteten Zyklus bildet. Ein gemischter Graph ist genau dann azyklisch, wenn er keine Zyklen hat.

Dies ist alles Standard und es gibt viele veröffentlichte Artikel, die azyklische gemischte Grafiken erwähnen. Daher muss der folgende Algorithmus zum Testen der Azyklizität gemischter Graphen bekannt sein:

Wiederholen Sie die folgenden Schritte:

  • Entfernen Sie alle Scheitelpunkte, die keine ankommenden gerichteten Kanten und keine ungerichteten Kanten aufweisen, da sie nicht Teil eines Zyklus sein können.
  • Wenn ein Scheitelpunkt keine ankommenden gerichteten Kanten, aber genau eine ankommende ungerichtete Kante hat, muss jeder Zyklus, der die ungerichtete Kante verwendet, an dieser Kante eintreten. Ersetzen Sie die ungerichtete Kante durch eine ankommende gerichtete Kante.

Stoppen Sie, wenn keine weiteren Schritte ausgeführt werden können. Wenn das Ergebnis ein leerer Graph ist, muss der ursprüngliche Graph notwendigerweise azyklisch gewesen sein. Andernfalls kann man ausgehend von einem verbleibenden Scheitelpunkt bei jedem Schritt, der rückwärts durch eine ankommende Kante oder einer ungerichteten Kante folgt, die nicht zum Erreichen des aktuellen Scheitelpunkts verwendet wird, durch den Graphen zurückverfolgen, bis ein wiederholter Scheitelpunkt angezeigt wird. Die zwischen der ersten und der zweiten Wiederholung dieses Scheitelpunkts (in umgekehrter Reihenfolge) verfolgte Folge von Kanten bildet einen Zyklus im gemischten Graphen.

Der Wikipedia-Artikel über gemischte Graphen erwähnt azyklische gemischte Graphen, erwähnt jedoch nicht, wie sie getestet werden sollen. Deshalb möchte ich etwas zu diesem Algorithmus hinzufügen, aber dafür benötige ich eine veröffentlichte Referenz. Kann mir jemand sagen, wo es (oder ein anderer Algorithmus zum Testen der Azyklizität) in der Literatur vorkommt?

ds.algorithms reference-request graph-theory graph-algorithms directed-acyclic-graph David Eppstein
quelle
Was passiert, wenn ein Scheitelpunkt zwei ungerichtete Kanten und keine andere Kante aufweist? Zum Beispiel in einem ungerichteten Dreieck. Ich meine, decken die obigen Regeln diesen Fall ab?
Mateus de Oliveira Oliveira
Sie können an einem solchen Scheitelpunkt nichts ändern, bis ein anderer Scheitelpunkt die Regel anwendet, die eine der Kanten ausrichtet. Wenn Sie in einer Situation stecken bleiben, in der solche Eckpunkte existieren und Sie keine Regeln mehr anwenden können, enthält Ihr Diagramm einen Zyklus.
David Eppstein
Vielleicht würde es klarer machen, was passiert, wenn Ihr Diagramm ungerichtet ist. Eine Möglichkeit, um zu testen, ob es sich um einen Wald handelt, besteht darin, Blätter (Scheitelpunkte ersten Grades) und isolierte Scheitelpunkte zu entfernen, bis entweder ein leerer Graph (ein Wald) oder ein nichttrivialer 2-Kern (ein Subgraph, in dem alle Scheitelpunkte einen Grad ≥ 2 haben, die notwendigerweise einen Zyklus enthält). Der Algorithmus für gemischte Graphen degeneriert im ungerichteten Fall (mit der Ausnahme, dass er die Blätter ausrichtet, anstatt sie sofort zu entfernen), genau wie er im gerichteten Fall zu einem standardmäßigen topologischen Sortieralgorithmus degeneriert.
David Eppstein
Nicht sicher , ob Sie gesehen haben: Es gibt eine Post auf cs.stackexchange , die eine ähnliche Frage stellt ref . Der Antwortende gibt einen Algorithmus an, um einen Zyklus in einem gemischten Diagramm zu finden, indem ungerichtete Kanten ausgerichtet werden und das Diagramm verworfen wird, wenn es nicht vorhanden ist. Es gibt auch Papier (e) zur Bestimmung , ob ein gemischtes Diagramm stark orientierbar ref aber seltsam, kann nichts finden auf tatsächlich angeschlossene Komponenten in gemischten Graphen zu finden.
Quanquan Liu
Danke - nein, das hatte ich nicht gesehen. Die Frage "Finden Sie eine Orientierung, damit der Graph einen gerichteten Zyklus enthält" ist definitiv dieselbe, und der Algorithmus in der Antwort sieht korrekt aus. Aber anders als die, die ich beschreibe, ist es keine lineare Zeit.
David Eppstein

Antworten:

1

Das Auffinden von gemischten Zyklen in einem gemischten Graphen entspricht dem Auffinden von elementaren gerichteten Zyklen (mit einer Länge> = 3) in dem entsprechenden gerichteten Graphen. Das entsprechende gerichtete Diagramm wird aus dem gemischten Diagramm erhalten, indem jede ungerichtete Kante durch zwei gerichtete Kanten ersetzt wird, die in entgegengesetzte Richtungen zeigen. Beweis: (1) Jeder elementar gerichtete Zyklus (mit einer Länge> = 3) im Digraphen entspricht direkt einem gemischten Zyklus im gemischten Graphen. (2) Jeder gemischte Zyklus in dem gemischten Graphen enthält einen elementaren gemischten Zyklus mit einer Länge> = 3, und jeder derartige Zyklus entspricht direkt einem elementaren gerichteten Zyklus (mit einer Länge> = 3) in dem gerichteten Graphen. (1) und (2) beweisen zusammen beide Richtungen der Aussage, qed. Wir suchen also nach Referenzen, wie man (alle?) Elementarzyklen (mit einer Länge> = 3) in einem gerichteten Graphen berechnet.

Die Kommentare weisen darauf hin, dass cs.stackexchange einige Antworten auf diese Frage enthält, es jedoch unklar ist, wie die Ergebnisse in einer präzisen Antwort zusammengefasst werden sollen. Dieser Blog-Beitrag fasst die (wichtigsten?) Referenzen gut zusammen:

Algorithmus von R. Tarjan

Der früheste Algorithmus, den ich einbezog, wurde 1973 von R. Tarjan veröffentlicht.

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

Algorithmus von DB Johnson

Der Algorithmus von DB Johnson aus dem Jahr 1975 verbessert Tarjans Algorithmus durch seine Komplexität.

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

Im schlimmsten Fall hat Tarjans Algorithmus eine zeitliche Komplexität von O (n (e (c + 1)), während Johnsons Algorithmus angeblich in O ((n + e) ​​(c + 1)) bleibt, wobei n die Anzahl von ist Ecken, e ist die Anzahl der Kanten und c ist die Anzahl der Zyklen in der Grafik.

Algorithmus von KA Hawick und HA James

Der Algorithmus von KA Hawick und HA James aus dem Jahr 2008 verbessert Johnsons Algorithmus weiter und beseitigt seine Einschränkungen.

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

Im Gegensatz zu Johnsons Algorithmus kann der Algorithmus von KA Hawick und HA James Graphen verarbeiten, die Kanten enthalten, die an demselben Scheitelpunkt beginnen und enden, sowie mehrere Kanten, die dieselben beiden Scheitelpunkte verbinden.

Der Azyklizitätstest selbst scheint einfach zu sein: Berechnen Sie die stark verbundenen Komponenten des Graphen. Jeder (Elementar-) Zyklus ist vollständig in einer stark verbundenen Komponente enthalten. Eine stark verbundene Komponente enthält einen Elementarzyklus, wenn es sich nicht um einen ungerichteten Baum handelt.

David Eppsteins vorgeschlagener Algorithmus berechnet zusätzlich einen Elementarzyklus als Beweis und die obigen Algorithmen zählen alle Elementarzyklen auf. Jeder Scheitelpunkt oder jede Kante, die nicht in einem Elementarzyklus enthalten ist, könnte als Vorverarbeitungsschritt gelöscht werden, um die Geschwindigkeit der obigen Algorithmen zu verbessern. David Eppsteins Algorithmus könnte für diesen Zweck verwendet werden, aber selbst wenn er nur für die stark verbundenen Komponenten verwendet wird, werden nicht alle möglichen Scheitelpunkte oder Kanten gelöscht, die gelöscht werden können. Aber selbst wenn es dazu erweitert werden könnte (das Berechnen des blockgeschnittenen Baums ermöglicht zumindest das Löschen jedes möglichen Scheitelpunkts, der gelöscht werden kann), ist unklar, ob dies die Geschwindigkeit der obigen Algorithmen wirklich verbessern würde.

Thomas Klimpel
quelle
Erwähnt eine dieser Referenzen überhaupt gemischte Grafiken? Ich weiß, wie man Zyklen in gerichteten Graphen findet. Meine Frage betraf die Erweiterung dieser Algorithmen auf gemischte Graphen.
David Eppstein
@DavidEppstein Die Suche nach gemischten Zyklen in einem gemischten Diagramm entspricht der Suche nach Elementarzyklen (mit einer Länge> = 3) im entsprechenden gerichteten Diagramm. Es mag schwierig sein, eine Referenz für diese Aussage zu finden, aber es ist unkompliziert, diese Aussage zu beweisen. Ich habe jetzt die Aussage und ihren Beweis zur Antwort hinzugefügt. (Es wurde auch eine Bemerkung hinzugefügt, die nicht belegt, dass die Berechnung des Blockschnittbaums das Löschen aller möglichen Scheitelpunkte ermöglicht, ohne die Elementarzyklen zu beeinflussen.)
Thomas Klimpel
Ok, aber sie sind immer noch nicht linear.
David Eppstein
@DavidEppstein Der Azyklizitätstest selbst erfolgt in linearer Zeit. Aber Sie haben Recht, die Zeit, die einer dieser Algorithmen benötigt, um die erste Elementarschaltung (mit einer Länge> = 3) zu finden, ist nicht linear (im schlimmsten Fall). Schlimmer noch, die meisten verfügbaren Implementierungen von Johnsons Algorithmus scheinen mehr als die Zeit O ((n + e) ​​(c + 1)) zu verwenden, wenn sie auf einen einzelnen gerichteten Kreis angewendet werden (mit n Eckpunkten, e = n Kanten und c = 1 Elementar) Fahrräder). Dennoch sollte dies eine richtige Antwort sein, da Johnsons Artikel die am häufigsten zitierte Referenz für das Auffinden von Elementarkreisen zu sein scheint.
Thomas Klimpel