Gerichtete und ungerichtete Graphen erklärt

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Die beiden Definitionen im Vergleich

Der Unterschied zwischen einem gerichteten und einem ungerichteten Graphen steckt in einem einzigen Wort der Definition: ob das Paar, das zwei Knoten verbindet, geordnet ist. Alles Weitere in diesem Artikel, einschließlich der Frage, welche Algorithmen noch funktionieren, ist eine Folge dieses Wortes.

Ein ungerichteter Graph ist das Standardobjekt aus dem Leitfaden zu Knoten und Kanten. Nach Diestels Graph Theory:

G = (V, E)      mit   E ⊆ [V]²      eine Kante ist ein ungeordnetes Paar {u, v}

Ein gerichteter Graph, auch Digraph genannt, ersetzt das ungeordnete Paar durch ein geordnetes:

D = (V, A)      mit   A ⊆ V × V      ein Bogen ist ein geordnetes Paar (u, v)

Da (u, v) und (v, u) verschiedene geordnete Paare sind, können beide gleichzeitig vorhanden sein; von einem Digraphen, der beide enthält, sagt man, er habe ein Digon zwischen u und v. In der ungerichteten Welt gibt es nichts zu unterscheiden: {u, v} und {v, u} sind dieselbe Menge, also existiert die Kante einmal oder gar nicht.

Diestel gibt eine allgemeinere Formulierung an, die man kennen sollte, weil sie den Kontakt mit echten Daten übersteht. Ein gerichteter Graph ist ein Paar (V, E) disjunkter Mengen zusammen mit zwei Abbildungen

init: E → V        ordnet jeder Kante ihren Anfangsknoten zu
ter:  E → V        ordnet jeder Kante ihren Endknoten zu

Hier ist ein Bogen ein eigenständiges Objekt statt eines Paares, daher erlaubt die Definition parallele Bögen und Schleifen ohne jede Sonderregel. Sie ist das gerichtete Gegenstück zur Definition über eine Inzidenzfunktion, die Multigraphen benötigen, und der Grund, warum ein Flugplan mit drei separaten täglichen Flügen von A nach B immer noch ein einwandfreier Digraph ist.

Die formale Beziehung zur Logik ist exakt und verdient es, einmal ausgesprochen zu werden: Ein ungerichteter Graph ohne Schleifen ist genau eine irreflexive symmetrische Relation auf V, während ein Digraph eine beliebige binäre Relation auf V ist. Richtung entsteht, sobald man nicht mehr darauf besteht, dass die Relation symmetrisch ist.

Diese beiden Graphen sind das durchgehende Beispiel für den gesamten Artikel. Der Digraph ist

V = {A, B, C, D, E}
A = { (A,B), (B,C), (C,A), (C,D), (D,E), (E,D) }        6 Bögen

und der ungerichtete Graph links ist sein zugrunde liegender Graphmit 5 Kanten, da die entgegengesetzten Bögen zwischen D und E zur einzigen Kante {D, E} werden.

2. Kanten, Bögen, Anfangs- und Endknoten

Mit der Definition ändert sich auch das Vokabular, und die Änderungen sind keine bloße Dekoration. Bang-Jensen und Gutins Digraphs, das Standardwerk zur gerichteten Seite, achtet sorgfältig auf getrennte Begriffe, damit eine Aussage nie mehrdeutig ist, welches Objekt sie meint.

Zwei Begriffe verdienen eine eigene Zeile, weil sie ständig verwechselt werden. Ein orientierter Graph ist ein Digraph ohne Digone: Man hat einen ungerichteten Graphen genommen und für jede Kante eine Richtung gewählt. Jeder orientierte Graph ist ein Digraph, aber ein Digraph, der sowohl (u,v) als auch (v,u) enthält, ist kein orientierter Graph. Diese Unterscheidung ist das ganze Thema von Abschnitt 5.

3. Der Grad teilt sich in zwei

In einem ungerichteten Graphen zählt der Grad eines Knotens die Kantenenden, die an ihm zusammentreffen, und das Handschlaglemma besagt, dass diese Zahlen sich zur doppelten Kantenzahl summieren. In einem Digraphen hat jeder Bogen einen Anfangs- und einen Endknoten statt zweier symmetrischer Enden, deshalb teilt sich die eine Zählung in zwei:

• Ausgangsgrad d+(v): die Anzahl der Bögen mit Anfangsknoten v.
• Eingangsgrad d-(v): die Anzahl der Bögen mit Endknoten v.

und auch die eine Identität teilt sich in zwei:

ungerichtet    ∑v∈V deg(v)   =  2m           jede Kante hat zwei Enden

gerichtet      ∑v∈V d+(v)  =  ∑v∈V d-(v)  =  |A|
                                             jeder Bogen hat einen Anfangs- und einen Endknoten

Der fehlende Faktor 2 bringt viele aus dem Konzept. Es ist kein anderer Satz, sondern dasselbe doppelte Abzählen, angewandt auf eine Menge, deren Elemente jetzt zu zwei getrennten Summen beitragen statt zweimal zu einer.

Prüfen Sie es am durchgehenden Beispiel. Die Ausgangsgrade sind A 1, B 1, C 2, D 1, E 1, zusammen 6. Die Eingangsgrade sind A 1, B 1, C 1, D 2, E 1, ebenfalls zusammen 6, und das ist die Anzahl der Bögen. Im zugrunde liegenden ungerichteten Graphen sind die Grade 2, 2, 3, 2, 1, zusammen 10, also das Doppelte seiner 5 Kanten.

Daraus ergeben sich sofort zwei benannte Knotentypen, die in der ungerichteten Welt überhaupt kein Gegenstück haben:

• Eine Quelle hat Eingangsgrad 0: Nichts zeigt auf sie.
• Eine Senke hat Ausgangsgrad 0: Sie zeigt auf nichts.

Quellen und Senken sind die Ein- und Austrittspunkte von Flussnetzwerken sowie Anfangs- und Endpositionen einer topologischen Ordnung. In einem ungerichteten Graphen lassen sich diese Begriffe schlicht nicht ausdrücken.

4. Was sich in Matrix und Liste ändert

Die Richtung zeigt sich in der Speicherung so deutlich wie in der Definition, und die Unterschiede sind jene, die Cormen, Leiserson, Rivest und Stein in Introduction to Algorithms darlegen.

Die Adjazenzmatrix. Bei einem ungerichteten Graphen ist die Matrix stets symmetrisch, A = AT, weil {u, v} und {v, u} dieselbe Kante sind. Bei einem Digraphen ist sie es im Allgemeinen nicht, und diese Asymmetrie trägt echte Information:

• Zeilensummen sind Ausgangsgrade, Spaltensummen sind Eingangsgrade. Im ungerichteten Fall liefern beide den Grad, weshalb die Unterscheidung dort nie aufkommt.
• Die Transponierte AT ist genau der umgekehrte Digraph, in dem jeder Bogen umgedreht ist. Einen ungerichteten Graphen umzukehren bewirkt nichts, was nur eine andere Art ist zu sagen, dass A = AT.
• Der Eintrag (Ak)uv zählt die Kantenzüge der Länge k von u nach v in beiden Welten, aber im gerichteten Fall müssen diese Kantenzüge die Pfeile beachten, daher weicht die Anzahl im Allgemeinen von (Ak)vu ab.

Die Adjazenzliste. Ein ungerichteter Graph speichert jede Kante zweimal, einmal in der Liste jedes Endpunkts, sodass die Listen 2m Einträge enthalten. Ein Digraph speichert jeden Bogen einmal, in der Liste des Anfangsknotens, was m Einträge ergibt. Das hat eine praktische Folge, die beim ersten Mal überrascht: Um einen Digraphen rückwärts zu durchlaufen, brauchen Sie eine zweite Struktur, die umgekehrte Adjazenzliste, denn die Liste eines Knotens sagt Ihnen, wohin Sie gehen können, nicht woher Sie kamen. Kosarajus Algorithmus für starke Zusammenhangskomponenten baut direkt auf dieser Beobachtung auf und durchläuft im zweiten Durchgang den umgekehrten Graphen.

Daraus folgen zwei Schranken. Ein einfacher ungerichteter Graph mit n Knoten hat höchstens n(n-1)/2 Kanten. Ein Digraph ohne Schleifen hat höchstens n(n-1) Bögen, genau doppelt so viele, weil jedes geordnete Paar jetzt ein eigener Platz ist.

5. Orientierungen und der zugrunde liegende Graph

Die beiden Welten sind durch zwei Konstruktionen verbunden, die in entgegengesetzte Richtungen gehen, und sie richtig zu benennen beseitigt viel Verwirrung.

• Zu einem Digraphen Dist sein zugrunde liegender Graph das, was entsteht, wenn man die Pfeile vergisst: Ersetzen Sie jeden Bogen (u, v) durch die Kante {u, v} und verwerfen Sie Duplikate. Der zugrunde liegende Graph des durchgehenden Beispiels hat 5 Kanten, eine weniger als die 6 Bögen des Digraphen, weil das Digon zwischen D und E zusammenfällt.
• Zu einem ungerichteten Graphen Gist eine Orientierung ein Digraph, den man erhält, indem man für jede Kante genau eine Richtung wählt. Das Ergebnis ist ein orientierter Graph: keine Digone, da jede Kante genau einen Bogen liefert.

Das sind keine zueinander inversen Operationen. Beim Übergang zum zugrunde liegenden Graphen gehen Informationen verloren, die keine Orientierung wiederherstellen kann, und ein Graph mit m Kanten hat 2m verschiedene Orientierungen, da jede Kante eine unabhängige binäre Wahl ist. Der zugrunde liegende Graph des durchgehenden Beispiels hat 5 Kanten und damit 32 Orientierungen, und der ursprüngliche Digraph ist nicht einmal eine davon, weil er ein Digon enthält.

Das wirft die Frage auf, die der nächste Abschnitt beantwortet. Ist unter diesen 2m Orientierungen irgendeine gut, in dem Sinne, dass man noch überallhin gelangt?

6. Der Satz von Robbins: Welche Straßen Einbahnstraßen werden können

1939 veröffentlichte Herbert Robbins im American Mathematical Monthly einen kurzen Aufsatz mit dem einprägsamen Titel „A theorem on graphs, with an application to a problem of traffic control“. Das Problem ist genau das eines Stadtplaners: Wenn jede Straße zur Einbahnstraße wird, können Autofahrer dann noch jeden Teil der Stadt erreichen?

Satz von Robbins. Ein zusammenhängender ungerichteter Graph besitzt genau dann eine stark zusammenhängende Orientierung, wenn er keine Brücke hat.

Eine Brücke, auch Trennkante genannt, ist eine Kante, deren Entfernen den Graphen zerfallen lässt. Ein zusammenhängender Graph ohne Brücken ist genau ein 2-fach kantenzusammenhängender Graph, in dem jede Kante auf einem Kreis liegt. (Der Zusammenhang ist hier wichtig: Ein unzusammenhängender Graph kann brückenfrei sein, ohne 2-fach kantenzusammenhängend zu sein.)

Eine Richtung des Beweises ist die leichte und lohnt einen Blick, weil sie das ganze Resultat erklärt. Angenommen, e = {u, v} ist eine Brücke, deren Entfernen den Graphen in eine Komponente mit u und eine Komponente mit v zerlegt. Jede Orientierung muss e in die eine oder die andere Richtung schicken. Wird daraus (u, v) , dann kann nichts auf der Seite von vje zur Seite von uzurückkehren, weil e die einzige Verbindung war und nun in die falsche Richtung zeigt. Wird daraus (v, u) , läuft dasselbe Argument umgekehrt. In beiden Fällen ist die Orientierung nicht stark zusammenhängend. Die Umkehrung, dass jeder brückenfreie zusammenhängende Graph tatsächlich eine stark zusammenhängende Orientierung besitzt , ist die gehaltvolle Hälfte; der Standardbeweis führt eine Tiefensuche aus und orientiert Baumkanten von der Wurzel weg und Rückwärtskanten zu ihr hin.

Das durchgehende Beispiel macht den Satz konkret. Sein zugrunde liegender Graph enthält das Dreieck A, B, C, das brückenfrei ist, aber die Kanten {C, D} und {D, E} sind beide Brücken. Nach dem Satz von Robbins ist daher keine Orientierung dieses Graphen stark zusammenhängend, und genau deshalb ist der Digraph in der Abbildung nicht stark zusammenhängend, ganz gleich, wie man die Pfeile neu zeichnet.

Nash-Williams verallgemeinerte das Resultat 1960: Jeder 2k-fach kantenzusammenhängende ungerichtete Graph besitzt eine k-fach bogenzusammenhängende Orientierung; der Satz von Robbins ist der Fall k = 1. Die praktische Lesart bleibt gleich. Einbahnstraßensysteme sind genau dort sicher, wo das Straßennetz Redundanz hat, und eine einzelne Straße, die einen Vorort mit dem Rest der Stadt verbindet, kann nie zur Einbahnstraße werden, ohne ihn abzuschneiden.

7. Zusammenhang wird zu drei verschiedenen Fragen

In einem ungerichteten Graphen ist Zusammenhang ein einfaches Ja oder Nein: Gibt es zwischen jedem Knotenpaar einen Weg? Die Richtung zerlegt das in eine Hierarchie. Die Klassifikation geht auf Harary, Norman und Cartwrights Structural Models zurück und ist das Stück Digraphentheorie, das am häufigsten übersprungen und am häufigsten gebraucht wird.

Jede Bedingung impliziert die darunterliegende, also folgt aus stark einseitig und aus einseitig schwach. Das durchgehende Beispiel liegt genau in der Mitte der Hierarchie, und das ist in der Praxis der typische Fall: Man kommt vom Dreieck A, B, C hinaus zu D und E, aber nie zurück.

Die nützliche Verfeinerung besteht darin, nicht mehr nach dem ganzen Digraphen, sondern nach seinen Teilen zu fragen. Eine starke Zusammenhangskomponente, kurz SCC, ist eine maximale Knotenmenge, in der jeder Knoten jeden anderen erreicht. Jeder Digraph zerfällt eindeutig in SCCs, und wenn man jede davon zu einem einzigen Knoten zusammenzieht, entsteht die Kondensation, die stets azyklisch ist. Diese letzte Tatsache ist kein Zufall: Hätte die Kondensation einen Kreis, würde jede Komponente darauf jede andere erreichen, und sie wären von Anfang an eine einzige SCC gewesen.

Das Finden der SCCs benötigt lineare Zeit. Tarjans Arbeit „Depth-first search and linear graph algorithms“ von 1972 erledigt es in einer einzigen Tiefensuche mit Low-Link-Werten, und das Verfahren von Kosaraju und Sharir braucht zwei Durchläufe, den zweiten über den umgekehrten Digraphen. Beide laufen in O(n + m), und beide haben kein ungerichtetes Gegenstück, weil sich in einem ungerichteten Graphen die Zusammenhangskomponenten aus jedem einzelnen Durchlauf ergeben.

8. Kreise, DAGs und topologische Ordnung

Das Wort „Kreis“ bedeutet stillschweigend etwas Strengeres, sobald Pfeile im Spiel sind, und diese Lücke verursacht echte Bugs.

In einem einfachen ungerichteten Graphen ist ein Kreis ein geschlossener Kantenzug ohne wiederholten Knoten und braucht mindestens drei Knoten, da das Hin- und Zurückgehen entlang einer Kante nicht als Kreis gilt. Ein ungerichteter Graph ohne Kreise ist ein Wald, und ein zusammenhängender ist ein Baum.

In einem Digraphen muss ein gerichteter Kreis den Pfeilen den ganzen Weg entlang folgen, und ein Digon zählt: Die beiden Bögen (D, E) und (E, D) bilden einen gerichteten Kreis der Länge 2. Ein Digraph ohne gerichtete Kreise ist ein DAG, ein gerichteter azyklischer Graph, und DAGs haben eine Eigenschaft, die in der ungerichteten Welt nichts besitzt:

Ein Digraph besitzt genau dann eine topologische Ordnung, also eine lineare Anordnung seiner Knoten, in der jeder Bogen nach vorn zeigt, wenn er azyklisch ist.

Kahns Arbeit von 1962 in den Communications of the ACM lieferte den Standardalgorithmus: Nehmen Sie wiederholt einen Knoten mit Eingangsgrad 0, geben Sie ihn aus und löschen Sie ihn samt seinen ausgehenden Bögen. Wird der Digraph leer, ist die Ausgabe eine topologische Ordnung; bleibt der Vorgang mit übrigen Knoten stehen, liegt jeder verbleibende Knoten auf einem Kreis. Die Details stehen im Leitfaden zur topologischen Sortierung.

Daraus ergeben sich zwei Fallen:

• Dass der zugrunde liegende Graph einen Kreis hat, sagt nichts aus. Der zugrunde liegende Graph des durchgehenden Beispiels enthält das Dreieck A, B, C, und sein Digraph enthält dort tatsächlich einen gerichteten Kreis. Orientieren Sie dasselbe Dreieck aber als A → B, A → C, B → C und Sie haben einen DAG, dessen zugrunde liegender Graph immer noch einen Kreis enthält. Ungerichtete Kreiserkennung kann keine gerichtete Frage beantworten.
• Kreiserkennung ist ein anderer Algorithmus. In einem ungerichteten Graphen findet eine Tiefensuche einen Kreis, wenn sie auf einen bereits besuchten Knoten trifft, der nicht der Elternknoten ist, von dem sie kam. In einem Digraphen ist dieser Test falsch: Sie müssen eine Rückwärtskante zu einem Knoten finden, der noch auf dem aktuellen Rekursionsstapel liegt, denn ein Bogen zu einem bereits abgeschlossenen Knoten ist harmlos.

9. Welche Algorithmen sich übertragen lassen und welche nicht

Die praktische Frage ist, welche Teile des ungerichteten Werkzeugkastens den Wechsel überstehen. Das Muster ist klarer, als es zunächst scheint: Alles, was Kanten nur vorwärts folgt, lässt sich übertragen, und alles, was auf Symmetrie beruht, nicht.

Die Zeile zum minimalen Spannbaum erwischt auch erfahrene Leute. Die Algorithmen von Kruskal und Prim sind gierig auf einer symmetrischen Kostenstruktur, und keiner übersteht eine Orientierung. Die richtige gerichtete Frage ist die minimale aufspannende Arboreszenz: Wählen Sie eine Bogenmenge mit minimalem Gesamtgewicht, sodass jeder Knoten von einer festen Wurzel aus erreichbar ist. Chu und Liu 1965 sowie Edmonds 1967 lösten das Problem unabhängig voneinander, und der Algorithmus sieht einer sortierten Kantenabarbeitung überhaupt nicht ähnlich: Er wählt für jeden Knoten den billigsten eingehenden Bogen, zieht dann jeden entstehenden Kreis zusammen und wiederholt.

10. Die Wahl: Ist Ihre Relation symmetrisch?

Die Modellierungsfrage hat eine einzige Form: Wenn die Relation von u nach v gilt, muss sie dann auch von v nach u gelten? Wenn ja, verwenden Sie einen ungerichteten Graphen. Wenn nein, oder wenn Sie unsicher sind, verwenden Sie einen Digraphen, denn ein Digraph kann immer eine symmetrische Relation ausdrücken, aber nicht umgekehrt.

Ein Fall verdient besondere Aufmerksamkeit, weil er symmetrisch aussieht und es nicht ist. Eine ungerichtete Kante kann nur ein Gewicht tragen. Wenn sich die Kosten von u nach v von den Kosten für den Rückweg unterscheiden, ist die Beziehung wechselseitig, aber das Modell muss trotzdem gerichtet sein. Radfahren bergauf und bergab, Up- und Download über eine asymmetrische Leitung und der Währungstausch in die eine oder die andere Richtung sind alles wechselseitige Verbindungen mit zwei verschiedenen Kosten, und jede erzwingt einen Digraphen mit zwei Bögen unterschiedlichen Gewichts.

11. Umwandlung zwischen beiden

Drei Umwandlungen kommen ständig vor, und jede verliert oder erfindet etwas, dessen Sie sich bewusst sein sollten.

• Digraph zu ungerichtet (Symmetrisierung). Ersetzen Sie jeden Bogen durch eine Kante. Das erfindet Erreichbarkeit: Nach dem Symmetrisieren des durchgehenden Beispiels erreicht D den Knoten A, was im Original falsch war. Verwenden Sie es nur, wenn Sie wirklich eine Frage über die zugrunde liegende Struktur stellen wollen, etwa ob der Digraph schwach zusammenhängend ist. Eine strengere Variante behält nur die wechselseitigen Paare und liefert den „reziproken“ Graphen, der nichts erfindet, aber sehr viel verwirft.
• Ungerichtet zu Digraph (Orientierung). Wählen Sie eine Richtung pro Kante. Das zerstört die gegenseitige Erreichbarkeit, es sei denn, der Graph ist brückenfrei, und genau das ist der Satz von Robbins in Abschnitt 6.
• Ungerichtet als Digraph (Bogenverdopplung). Ersetzen Sie jede Kante {u, v} durch beide Bögen (u, v) und (v, u). Das tut fast jede Graphenbibliothek intern, und für Durchläufe und kürzeste Wege ist es korrekt. Aber jede Kante wird dadurch zu einem gerichteten Kreis der Länge 2, sodass jeder DAG-Test nun negativ ausfällt, jede Zusammenhangskomponente zu einer einzigen starken Zusammenhangskomponente wird und eine Kreiserkennung für jede einzelne Kante einen Kreis meldet. Die Darstellung ist in Ordnung; gerichtete Strukturalgorithmen darauf auszuführen, ist es nicht.

12. Häufige Fehler

• Die Adjazenzliste eines ungerichteten Graphen nur in eine Richtung aufbauen. Der wohl häufigste Graphen-Bug überhaupt. Wer eine Kantenliste einliest und nur adj[u].push(v) anhängt, erzeugt stillschweigend einen Digraphen, und die BFS findet dann keinen Weg entlang einer Kante, die sie sehen kann.
• Sie für einen gerichteten Graphen in beide Richtungen aufbauen. Derselbe Fehler umgekehrt und schwerer zu entdecken: Der Code läuft, die Wege sehen plausibel aus, und jede richtungsabhängige Antwort ist falsch.
• Ungerichtete Kreiserkennung auf einem Digraphen verwenden. Einen Kreis zu melden, sobald die DFS auf einen besuchten Nicht-Elternknoten trifft, markiert viele DAGs als zyklisch. Digraphen brauchen den Test auf Rückwärtskanten zum Rekursionsstapel.
• Annehmen, Erreichbarkeit sei symmetrisch. „Gibt es einen Weg von u nach v?“ und „Gibt es einen Weg von v nach u?“ sind in einem Digraphen zwei verschiedene Anfragen, und die Antwort auf die eine beantwortet nicht die andere.
• Vergessen, dass man den umgekehrten Graphen braucht. „Welche Knoten können v erreichen?“ lässt sich aus der Vorwärts-Adjazenzliste nicht ohne einen vollständigen Durchlauf beantworten. Bauen Sie die umgekehrte Liste einmal auf, wenn Sie diese Frage oft stellen.
• Auf einem Digraphen zum MST greifen. Kruskal und Prim haben keine gerichtete Version. Was Sie wollen, ist eine minimale Arboreszenz.
• Symmetrisieren, um eine Bibliothek wiederzuverwenden. Bequem, und es ändert die Antwort. Jede Umwandlung in Abschnitt 11 hat ihren Preis, setzen Sie sie also bewusst ein.

13. Glossar

15. Quellen

Die Definitionen, Sätze und Zuschreibungen oben stammen aus diesen Quellen, in chronologischer Reihenfolge.

1. Robbins, H. E. (1939). "A theorem on graphs, with an application to a problem of traffic control." American Mathematical Monthly 46(5), 281 bis 283. Der Orientierungssatz für brückenfreie Graphen in Abschnitt 6.
2. Ford, L. R. und Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics 8, 399 bis 404. Fluss, von Anfang an auf einem Digraphen formuliert.
3. Nash-Williams, C. St. J. A. (1960). "On orientations, connectivity and odd-vertex-pairings in finite graphs." Canadian Journal of Mathematics 12, 555 bis 567. Die Verallgemeinerung von Robbins auf k-fachen Bogenzusammenhang.
4. Kahn, A. B. (1962). "Topological sorting of large networks." Communications of the ACM 5(11), 558 bis 562.
5. Chu, Y. J. und Liu, T. H. (1965). "On the shortest arborescence of a directed graph." Scientia Sinica 14, 1396 bis 1400.
6. Harary, F., Norman, R. Z. und Cartwright, D. (1965). Structural Models: An Introduction to the Theory of Directed Graphs. New York: Wiley. Quelle der Einteilung in starken, einseitigen und schwachen Zusammenhang.
7. Edmonds, J. (1967). "Optimum branchings." Journal of Research of the National Bureau of Standards 71B(4), 233 bis 240.
8. Tarjan, R. E. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing 1(2), 146 bis 160. Starke Zusammenhangskomponenten in linearer Zeit.
9. Sharir, M. (1981). "A strong-connectivity algorithm and its applications in data flow analysis." Computers & Mathematics with Applications 7(1), 67 bis 72. Das Zwei-Durchlauf-Verfahren, das meist mit Kosarajus Namen verbunden wird.
10. Brin, S. und Page, L. (1998). "The anatomy of a large-scale hypertextual Web search engine." Computer Networks and ISDN Systems 30(1 bis 7), 107 bis 117. PageRank auf dem Web-Digraphen.
11. West, D. B. (2001). Introduction to Graph Theory, 2. Auflage. Upper Saddle River: Prentice Hall.
12. Bondy, J. A. und Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
13. Bang-Jensen, J. und Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2. Auflage. London: Springer. Das Standardwerk zur Terminologie gerichteter Graphen.
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage. Cambridge, Massachusetts: MIT Press. Quelle der Darstellungskosten in Abschnitt 4.
15. Chartrand, G., Lesniak, L. und Zhang, P. (2015). Graphs & Digraphs, 6. Auflage. Boca Raton: CRC Press. Ein Lehrbuch, das beide Objekte nebeneinander entwickelt.
16. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer. Quelle der beiden in Abschnitt 1 zitierten Definitionen.