Einführung in die Graphentheorie

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Was die Graphentheorie eigentlich untersucht

Die Graphentheorie untersucht eine einzige, sehr kleine Idee: eine Sammlung von Objekten und eine Aufzeichnung darüber, welche Paare davon miteinander verbunden sind. Das ist das ganze Fachgebiet. Was es anderthalb Jahrhunderte Mathematik wert macht, ist die Tatsache, dass sich eine enorme Zahl praktischer Fragen als Fragen genau darüber herausstellt, und über nichts sonst.

Betrachten Sie vier Probleme, die nichts miteinander zu tun zu haben scheinen. Ein Lieferdienst sucht die kürzeste Route zwischen zwei Depots. Ein Compiler braucht die Reihenfolge, in der die Module eines Projekts gebaut werden müssen. Eine Biologin möchte wissen, welche Proteine direkt oder über Zwischenstufen miteinander interagieren. Ein Netzbetreiber möchte wissen, welches Kabel eine Region isolieren würde, wenn es durchtrennt wird. Als Geschichten haben diese Fälle nichts gemeinsam. Strukturell sind sie dieselbe Handvoll Probleme, gestellt über dieselbe Art von Objekt, und die Algorithmen, die sie beantworten, sind austauschbar. Diese Übertragbarkeit ist der Grund, warum das Fach früh gelehrt und überall eingesetzt wird: Sobald eine Situation als Graph formuliert ist, steht auf einen Schlag ein großer Katalog von Ergebnissen zur Verfügung, und keinem davon ist es wichtig, wofür die Knoten ursprünglich standen.

Achten Sie darauf, was das Bild auf der rechten Seite nicht enthält. Die Orte haben sich verschoben, die Straßen sind gerade, und nichts hält fest, dass eine Straße doppelt so lang ist wie eine andere. Wenn diese Tatsachen für Ihre Frage wichtig sind, müssen Sie sie ausdrücklich wieder hinzufügen, als Zahlen an den Kanten. Wenn nicht, ist genau das Weglassen das, was das Problem handhabbar macht.

Dieser Artikel ist ein Einführungskurs auf einer einzigen Seite: die Definitionen in der richtigen Reihenfolge, die kleinen Ergebnisse, auf denen alles andere aufbaut, wie Graphen in echtem Code gespeichert und durchsucht werden, die klassischen Probleme und eine ehrliche Landkarte dessen, welche Fragen ein Computer in Sekunden beantworten kann und welche er überhaupt nicht beantworten kann. Jeder Abschnitt verlinkt auf einen vertiefenden Artikel, falls Sie zu diesem Thema mehr wissen möchten.

2. Die Definition und was sie bewusst weglässt

Fast jede populäre Darstellung sagt, ein Graph seien „durch Linien verbundene Punkte“. Dieses Bild ist nützlich, und es ist zugleich der Grund, warum viele Menschen ein paar Wochen später nicht weiterkommen: Die Punkte und Linien sind eine Zeichnung des Objekts, nicht das Objekt selbst. Das Objekt ist ein Paar von Mengen. Diestels Graph Theory, das Standardwerk für Fortgeschrittene, formuliert es in seiner klarsten Form:

Ein Graph ist ein Paar G = (V, E) von Mengen mit E ⊆ [V]², wobei [V]² die Menge aller 2-elementigen Teilmengen von V ist.

Ausgepackt besagt das vier Dinge:

• V ist eine Menge von Objekten, genannt Knoten (oder Ecken). Über sie wird überhaupt nichts vorausgesetzt. Es können Städte, Menschen, Atome, Webseiten oder ganze Zahlen sein. Die Theorie blickt nie in einen Knoten hinein; sie muss nur zwei Knoten voneinander unterscheiden können.
• E ist eine Menge von 2-elementigen Teilmengen von V. Eine Kante ist buchstäblich die Menge {u, v}. Sie ist kein Pfeil und keine Kurve, und sie trägt keine Information außer der, welches Paar sie verbindet.
• Da E eine Mengeist, ist eine Kante entweder vorhanden oder nicht. Sie kann nicht zweimal vorkommen.
• Da jede Kante zwei verschiedene Elementehat, verbindet keine Kante einen Knoten mit sich selbst.

Diese beiden letzten Folgerungen sind keine Zusatzregeln, die jemand ergänzt hat; sie ergeben sich direkt aus der Mengenlehre, und ein Graph, der sie erfüllt, heißt einfach. Mehrfachkanten oder Schleifen zuzulassen bedeutet, die Definition selbst zu ändern, und genau das tun Multigraphen in Abschnitt 5.

Zwei weitere Notationen tauchen überall auf. Man schreibt V(G) und E(G) , wenn mehrere Graphen im Spiel sind. Und die beiden Größenmaße haben Namen: Die Anzahl der Knoten ist die Ordnung des Graphen, die Anzahl der Kanten seine Größe, in fast allen Algorithmentexten abgekürzt zu n = |V| und m = |E|.

Was die Definition weglässt, ist ebenso aufschlussreich wie das, was sie enthält. Es gibt keine Geometrie, also sind zwei Zeichnungen desselben Graphen derselbe Graph, auch wenn die eine wie eine Spirale und die andere wie ein Gitter aussieht. Es gibt keine Reihenfolge der Knoten. Es gibt keine Entfernungen, Kapazitäten oder Kosten; diese kommen aus einer zusätzlichen Funktion, meist geschrieben als w: E → ℝ, die angefügt wird, wenn ein Problem sie braucht. Das nackte Objekt ist absichtlich karg, und genau diese Kargheit sorgt dafür, dass Sätze darüber so breit anwendbar sind. Der begleitende Leitfaden zu Knoten und Kanten arbeitet dieselbe Definition ausführlicher durch.

3. Wie alles begann: sieben Brücken und ein unmöglicher Spaziergang

Das Fachgebiet hat einen Geburtstag. Im Jahr 1736 reichte Leonhard Euler, damals an der Akademie in Sankt Petersburg, eine Arbeit mit dem Titel Solutio problematis ad geometriam situs pertinentisein, „die Lösung eines Problems, das die Geometrie der Lage betrifft“. Das Problem stammte aus der preußischen Stadt Königsberg, dem heutigen Kaliningrad. Der Fluss Pregel teilte die Stadt in vier Landstücke, die durch sieben Brücken verbunden waren, und die Bürger vertrieben sich die Zeit mit einer Frage: Kann man durch die Stadt spazieren und dabei jede Brücke genau einmal überqueren?

Eulers erster Schritt ist genau der Schritt, um den es in diesem ganzen Artikel geht. Größe und Form der Landstücke sind unerheblich, die Länge der Brücken ist unerheblich, und das Einzige, was zählt, ist, welches Landstück mit welchem verbunden ist und wie oft. Streicht man den Rest, bleiben vier Objekte und sieben Verbindungen, die moderne Lehrbücher als Multigraphen mit vier Knoten und sieben Kanten zeichnen.

Sein Argument ist kurz genug, um es vollständig wiederzugeben. Angenommen, der Spaziergang existiert, und nehmen wir ein beliebiges Landstück, das weder sein Anfang noch sein Ende ist. Jedes Mal, wenn der Spaziergang dort ankommt, muss er es auch wieder verlassen, also werden die Brücken an diesem Landstück paarweise benutzt, und ihre Anzahl muss gerade sein. In Königsberg hatten die vier Landstücke 5, 3, 3 und 3 Brücken, alle ungerade. Ein Spaziergang hat nur zwei Enden, also dürfen höchstens zwei Landstücke eine ungerade Anzahl haben. Vier sind zu viele, und ein solcher Spaziergang existiert nicht.

Euler formulierte auch die Umkehrung, bewies sie aber nicht; diese Lücke blieb offen, bis Carl Hierholzer einen konstruktiven Beweis lieferte, der 1873 posthum veröffentlicht wurde. Die moderne Aussage ist klar: Ein zusammenhängender Graph besitzt einen geschlossenen Weg, der jede Kante genau einmal benutzt, einen Eulerkreis, genau dann, wenn jeder Knoten geraden Grad hat, und einen offenen, einen Eulerweg, genau dann, wenn genau zwei Knoten ungeraden Grad haben. Die ganze Geschichte steht im Leitfaden zu Eulerweg und Eulerkreis.

Das folgende Jahrhundert füllte die Grundlagen auf, von Kirchhoffs Spannbäumen im Jahr 1847 über Sylvester, der 1878 das Wort „Graph“ aus der Chemie entlehnte, bis zu Kőnigs erstem Lehrbuch im Jahr 1936. Diese Geschichte wird in der Geschichte der Graphentheorieerzählt.

4. Das Vokabular und der erste Satz

Der Rest dieses Artikels verwendet ein durchgehendes Beispiel, einen Graphen mit sieben Knoten und acht Kanten. Er ist klein genug, um jede Aussage von Hand zu überprüfen, und groß genug, um interessant zu sein.

V = {A, B, C, D, E, F, G}                          n = 7
E = { {A,B}, {A,C}, {B,C}, {B,D}, {C,E},
      {D,E}, {D,F}, {F,G} }                        m = 8

Hier sind die Begriffe, jeder allein aus den beiden Mengen definiert:

• Benachbart (adjazent). Zwei Knoten, die durch eine Kante verbunden sind. B und D sind benachbart, A und D nicht.
• Inzident. Eine Kante ist inzident zu jedem ihrer beiden Endknoten. Adjazenz setzt einen Knoten mit einem Knoten in Beziehung, Inzidenz einen Knoten mit einer Kante, und Anfänger verwechseln die beiden regelmäßig.
• Nachbarschaft. N(v), die Menge der zu v benachbarten Knoten. Hier N(D) = {B, E, F}.
• Grad. deg(v), die Anzahl der Kantenenden, die in v zusammentreffen, in einem einfachen Graphen also schlicht |N(v)|. Hier deg(B) = 3 und deg(G) = 1.
• Blatt und isolierter Knoten. Grad 1, wie G, und Grad 0. Isolierte Knoten sind zulässig, und sie sind das am häufigsten verlorene Stück Information, wenn ein Graph aus einer Kantenliste aufgebaut wird, denn eine Kantenliste hat keine Möglichkeit, sie zu erwähnen.
• Minimal- und Maximalgrad. δ(G) und Δ(G), hier 1 bei G und 3 bei B, C und D.

Mit dem Begriff des Grades ist der erste Satz nur noch eine Zeile entfernt. Die sieben Grade summieren sich zu 2 + 3 + 3 + 3 + 2 + 2 + 1 = 16, genau das Doppelte der acht Kanten, und das ist kein Zufall dieses speziellen Graphen.

Diese Technik, eine Sammlung auf zwei Arten zu zählen, heißt doppeltes Abzählen, und sie ist das Arbeitspferd der elementaren Kombinatorik. Das Lemma hat eine Folgerung, die beim ersten Mal überrascht: Die Anzahl der Knoten mit ungeradem Grad ist immer gerade. Hier sind es B, C, D und G, also vier. Der Grund ist Arithmetik: Die Summe ist gerade, und die Knoten mit geradem Grad tragen einen geraden Betrag bei, also müssen die Knoten mit ungeradem Grad zusammen ebenfalls einen geraden Betrag beitragen, und dafür braucht es eine gerade Anzahl von ihnen. Alltagssprachlich: Die Zahl der Menschen in einem Raum, die einer ungeraden Zahl anderer die Hand geschüttelt haben, ist gerade. Eulers Königsberg-Argument ist genau diese Folgerung, angewandt auf einen Spaziergang.

5. Die Graphenfamilien

Die nackte Definition aus Abschnitt 2 ist die restriktivste. Jedes echte Modellierungsproblem braucht früher oder später eine Variante, und jede Variante ist eine bestimmte, benannte Änderung dessen, was eine Kante sein darf. Zu wissen, in welcher Familie man sich befindet, entscheidet darüber, welche Algorithmen überhaupt anwendbar sind; das ist also kein Vokabular um seiner selbst willen.

Einfache Graphen sind der Standardfall: keine Schleifen, keine Mehrfachkanten, und jedes Ergebnis in einem Lehrbuch ohne weiteren Zusatz bezieht sich auf sie. Multigraphen erlauben parallele Kanten, und Pseudographen erlauben zusätzlich Schleifen. Königsberg braucht tatsächlich einen Multigraphen, da zwei seiner Landstücke durch zwei Brücken verbunden waren, und eine Schleife erhöht den Grad ihres Knotens um 2, weil beide Enden dort ansetzen. Siehe einfache Graphen und Multigraphen.

Gerichtete Graphen, auch Digraphen, ersetzen das ungeordnete Paar {u, v} durch das geordnete Paar (u, v), genannt Bogen, sodass ein Digraph eine Richtung, beide oder keine enthalten kann, und der Grad zerfällt in Eingangsgrad und Ausgangsgrad. Das ist das richtige Modell, wann immer die Beziehung nicht symmetrisch ist: Einbahnstraßen, „A folgt B“, „Modul A importiert Modul B“, „Aufgabe A muss vor Aufgabe B fertig sein“. Siehe gerichtete und ungerichtete Graphen.

Gewichtete Graphen fügen eine Funktion w hinzu, die jeder Kante eine Zahl zuordnet: Kilometer, Minuten, Preis, Kapazität, Ähnlichkeit. Algorithmen haben zu diesen Zahlen klare Ansichten. Der Dijkstra-Algorithmus verlangt, dass sie nicht negativ sind, Bellman-Ford toleriert negative Werte, aber keine negativen Kreise, und die Breitensuche ignoriert sie vollständig. Genau deshalb ist es einer der häufigsten Fehler in Anfängercode, BFS auf einem gewichteten Graphen laufen zu lassen und das Ergebnis als kürzesten Weg auszugeben. Siehe gewichtete und ungewichtete Graphen.

Bipartite Graphen teilen die Knotenmenge in zwei Teile, wobei jede Kante zwischen ihnen verläuft. Studierende und Kurse, Bewerber und Stellen, Käufer und Produkte: Jede zweiseitige Zuordnungssituation ist bipartit. Ein Graph ist genau dann bipartit, wenn er keinen ungeraden Kreis enthält, und eine einzige Breitensuche, die die Knoten mit zwei Farben einfärbt, entscheidet das in linearer Zeit.

Vollständige Graphen, geschrieben Kn, besitzen jede mögliche Kante. Da eine Kante eine Auswahl von 2 aus n Knoten ist, beträgt die Anzahl n(n-1)/2, also hat K5 10 Kanten und K100 hat 4.950. Das ist zugleich die Obergrenze für jeden einfachen Graphen mit n Knoten, und daran wird die Dichte eines Graphen gemessen.

Bäume sind zusammenhängende Graphen ohne Kreise, das Thema von Abschnitt 8. DAGs, gerichtete azyklische Graphen, sind Digraphen ohne gerichteten Kreis, und sie haben die Form jeder Abhängigkeit und jedes Zeitplans: Tabellenformeln, Build-Ziele, Git-Commits und die Operationen eines neuronalen Netzes sind allesamt DAGs, und der Algorithmus, der sie in eine gültige Reihenfolge bringt, ist die topologische Sortierung.

Eine weitere Familie sollte man beim Namen kennen: Planare Graphen lassen sich ohne Kantenkreuzungen zeichnen, was für Schaltungslayouts und das Färben von Landkarten wichtig ist und worauf Abschnitt 12 zurückkommt.

6. Kantenfolgen, Kantenzüge, Pfade und Kreise

Vier Begriffe beschreiben die Bewegung durch einen Graphen. Umgangssprachlich werden sie austauschbar verwendet, doch sie bedeuten vier verschiedene Dinge. Sie sauber auseinanderzuhalten, erspart später erstaunlich viel Verwirrung, denn Sätze werden mit dem präzisen Begriff formuliert, und der Unterschied zwischen ihnen ist oft der gesamte Inhalt des Ergebnisses.

• Eine Kantenfolge ist jede Folge von Knoten, in der aufeinanderfolgende Knoten benachbart sind. Nichts ist verboten. Eine Kantenfolge darf dieselbe Kante überqueren und denselben Knoten so oft wieder besuchen, wie sie will.
• Ein Kantenzug ist eine Kantenfolge ohne wiederholte Kante. Knoten dürfen sich weiterhin wiederholen. Eulers Brückenproblem fragt nach einem Kantenzug, der jede Kante benutzt; genau genommen ist es also ein Euler-Kantenzug und kein Euler-Pfad (der deutsche Standardbegriff Eulerweg meint den Kantenzug).
• Ein Pfad ist eine Kantenfolge ohne wiederholten Knoten, was automatisch auch wiederholte Kanten ausschließt. Wenn jemand von „der Route von A nach G“ spricht, ist das gemeint.
• Ein Kreis ist ein geschlossener Pfad: Er beginnt und endet im selben Knoten und wiederholt sonst nichts. Im Beispiel ist B, C, E, D, B ein Kreis der Länge 4, und A, B, C, A ist ein Dreieck, ein Kreis der Länge 3.

Die Länge jeder dieser Routen ist die Anzahl ihrer Kanten, nicht die Anzahl ihrer Knoten, und genau hier lauert ein Off-by-one-Fehler. Der Abstand d(u, v) ist die Länge eines kürzesten Pfades. Hier gilt d(A, G) = 4, entlang A, B, D, F, G; die Route A, C, E, D, F, G kommt ebenfalls an, benutzt aber fünf Kanten, ist also ein Pfad, aber kein kürzester. Der Durchmesser ist der größte Abstand zwischen zwei Knoten, eine kompakte Art auszudrücken, wie weit ein Netzwerk ausgedehnt ist.

Eine Tatsache folgt unmittelbar und wird ständig verwendet: Gibt es eine Kantenfolge von u nach v, dann gibt es auch einen Pfad von u nach v. Schneidet man die Schleife zwischen zwei Besuchen desselben Knotens heraus, erhält man eine kürzere Kantenfolge, also endet diese Operation bei einer ohne wiederholten Knoten. Deshalb betrachten Erreichbarkeitsalgorithmen Kantenfolgen überhaupt nicht.

7. Zusammenhang, Komponenten und die Kanten, die man nicht verlieren darf

Ein Graph ist zusammenhängend , wenn jeder Knoten von jedem anderen aus erreichbar ist. Ist er es nicht, zerfällt er in Zusammenhangskomponenten, die maximalen Teile, die in sich zusammenhängend sind. Der Zusammenhang ist das Erste, was man bei jedem Graphen prüfen sollte, den man nicht selbst erstellt hat, denn erstaunlich viele reale Datensätze kommen in mehreren Teilen an, und die meisten gemeldeten Fehler der Form „der Algorithmus hat unendlich zurückgegeben“ sind genau diese Tatsache, auf die harte Tour entdeckt.

Innerhalb eines zusammenhängenden Graphen sind manche Teile der Struktur kritischer als andere. Eine Brücke ist eine Kante, deren Entfernen die Anzahl der Komponenten erhöht, und ein Schnittknoten, auch Artikulationspunkt, ist ein Knoten, dessen Entfernen dasselbe bewirkt. Das sind die einzelnen Ausfallpunkte, und sie zu finden, ist die übliche erste Analyse jedes Netzwerks, dessen Zuverlässigkeit wichtig ist.

Im durchgehenden Beispiel sind die Kanten DF und FG Brücken, und D und F sind Schnittknoten. Achten Sie darauf, was keine Brücke ist: keine der fünf Kanten, die auf einem Kreis liegen, denn ein Kreis bietet immer einen Umweg. Das ist die allgemeine Regel, und sie verdient es, als Tatsache formuliert zu werden, nicht nur als Beobachtung. Eine Kante ist genau dann eine Brücke, wenn sie auf keinem Kreis liegt. Dieselbe Intuition erklärt, warum Redundanz in realen Netzwerken in Kreisen gemessen wird: Eine zweite Route ist ein Kreis durch die erste.

Bei gerichteten Graphen spaltet sich der Begriff in zwei auf: Ein Digraph ist schwach zusammenhängend , wenn beim Ignorieren der Bogenrichtungen ein zusammenhängender Graph übrig bleibt, und stark zusammenhängend , wenn jeder Knoten jeden anderen erreicht, indem er den Bögen in der richtigen Richtung folgt. Tarjans Algorithmus von 1972 findet die starken Zusammenhangskomponenten in linearer Zeit, und in einem Abhängigkeitsgraphen ist eine solche Komponente mit mehr als einem Knoten genau eine zirkuläre Abhängigkeit.

Rechnerisch ist all das günstig. Ein einziger Breiten- oder Tiefensuchdurchlauf beschriftet jede Komponente in O(n + m), und Brücken sowie Schnittknoten ergeben sich aus einer einzigen Tiefensuche, erweitert um Tarjans Low-Link-Werte, ebenfalls in O(n + m). Es gibt selten einen Grund, den Zusammenhang nicht zu prüfen, bevor man irgendetwas anderes tut.

8. Bäume: der nützlichste Spezialfall

Ein Baum ist ein zusammenhängender Graph ohne Kreise. Er ist der mit Abstand wichtigste Spezialfall des Fachgebiets, zum einen, weil Bäume in der Informatik überall auftauchen, zum anderen, weil sehr viele schwere Probleme leicht werden, wenn die Eingabe zufällig ein Baum ist.

Bemerkenswert an Bäumen ist, wie viele unterschiedlich klingende Beschreibungen dieselben Objekte erfassen. Für einen Graphen G mit n Knoten sind alle folgenden Aussagen äquivalent, und jede davon kann als Definition dienen:

1. G ist zusammenhängend und hat keine Kreise.
2. G ist zusammenhängend und hat genau n - 1 Kanten.
3. G hat keine Kreise und hat genau n - 1 Kanten.
4. Zwischen jedem Knotenpaar gibt es genau einen Pfad.
5. G ist zusammenhängend, und das Entfernen einer beliebigen Kante zerlegt ihn, also ist jede Kante eine Brücke.
6. G hat keine Kreise, und das Hinzufügen einer beliebigen neuen Kante erzeugt genau einen Kreis.

Die Äquivalenz wird als Kette von Implikationen bewiesen, dargestellt im Leitfaden zu Bäumen in der Graphentheorie. Zwei Folgerungen sollte man immer parat haben. Die Kantenzahl ist festgelegt, ein „Baum“ mit 100 Knoten und 120 Kanten ist also kein Baum, und irgendwo davor ist etwas schiefgelaufen. Und die Eindeutigkeit der Pfade ist der Grund, warum Baumprobleme leicht sind: Es gibt nichts zu suchen, weil es immer nur eine Route gibt.

Ein Wald ist ein azyklischer Graph, der nicht zusammenhängend sein muss, also eine disjunkte Vereinigung von Bäumen, und ein Wald mit n Knoten und c Komponenten hat genau n - c Kanten. Ein Spannbaum eines zusammenhängenden Graphen ist ein Teilgraph, der ein Baum ist und jeden Knoten enthält, das günstigste Gerüst, das den Graphen in einem Stück hält. Beide Traversierungen liefern nebenbei kostenlos einen, und wenn Kanten Gewichte tragen, ist das Finden des leichtesten das Problem des minimalen Spannbaums .

Bäume gibt es auch in einer gewurzelten Variante, bei der ein Knoten ausgezeichnet wird und die Begriffe Elternknoten, Kind, Vorfahr, Teilbaum und Tiefe verfügbar werden, wie in Dateisystemen, Syntaxbäumen und Heaps. Die Wurzelwahl ist eine Entscheidung, die über den Graphen gelegt wird, keine Eigenschaft des Graphen selbst, und genau darum geht es im Artikel über gewurzelte Bäume.

9. Wie ein Graph im Computer gespeichert wird

Alles bisher war Mathematik. Sobald eine Maschine eine Frage über einen Graphen beantworten muss, müssen Sie entscheiden, wie er im Speicher angeordnet wird, und diese Entscheidung ist kein Implementierungsdetail: Sie verändert die Kosten von Operationen um Faktoren von Tausenden, und eine schlecht passende Darstellung ist der häufigste Grund, warum ein korrekter Algorithmus zu langsam läuft. Es gibt drei Standarddarstellungen, und sie speichern genau dieselbe Information.

Die Kantenliste ist die ausgeschriebene Menge E. Sie ist kompakt, sie ist das, was eine CSV-Datei oder eine API liefert, und sie ist das, was der Kruskal-Algorithmus will, denn dieser sortiert Kanten nach Gewicht und fragt nie nach einem bestimmten Knoten. Ihre Schwäche: „Wer sind die Nachbarn von D?“ bedeutet, alle m Zeilen zu durchsuchen.

Die Adjazenzmatrix ist ein n-mal-n-Raster, in dem die Zelle (u, v) gleich 1 ist, wenn die Kante vorhanden ist. Ob zwei gegebene Knoten benachbart sind, ist ein einziger Zugriff, und bei ungerichteten Graphen ist die Matrix symmetrisch, speichert also jede Tatsache doppelt. Der Preis ist Speicher: n zum Quadrat Zellen, ob es Kanten gibt oder nicht. Sie ist außerdem das Tor zu spektralen Methoden, bei denen die Eigenwerte der Matrix oder der eng verwandten Laplace-Matrix Cluster und Zusammenhang offenlegen, das Thema von spektraler Graphentheorie im maschinellen Lernen.

Die Adjazenzliste hält für jeden Knoten die Liste seiner Nachbarn. Über die Nachbarn von v zu iterieren kostet O(deg v), was optimal ist, und der gesamte Speicherbedarf beträgt O(n + m). Das ist in der Praxis der Standard und die Darstellung, die jede der folgenden Traversierungen voraussetzt.

Was die Frage in der Praxis entscheidet, ist, dass reale Netzwerke dünn besetztsind: Die durchschnittliche Zahl der Nachbarn bleibt im zweistelligen Bereich, egal wie groß das Netzwerk wird, denn Kreuzungen haben drei oder vier Straßen, und Menschen haben eine begrenzte Zahl von Freunden. Für einen Graphen mit einer Million Knoten und fünf Millionen Kanten hält die Adjazenzliste etwa zehn Millionen Einträge, während die Matrix eine Billion Zellen bräuchte, mehrere Terabyte für einen Graphen, der sonst bequem in den Arbeitsspeicher passt. Verwenden Sie die Matrix, wenn der Graph klein, wirklich dicht oder für lineare Algebra bestimmt ist; sonst die Adjazenzliste. Die ausführlichere Behandlung, einschließlich komprimierter Zeilenformate (CSR), finden Sie unter Darstellung von Graphen.

Eine Adjazenzliste aus einer Kantenliste aufzubauen, dauert vier Zeilen, und der Kommentar in der Mitte ist genau der Teil, den Anfänger falsch machen:

edges = [('A','B'), ('A','C'), ('B','C'), ('B','D'),
         ('C','E'), ('D','E'), ('D','F'), ('F','G')]

graph = {v: [] for v in 'ABCDEFG'}   # bei V beginnen, damit isolierte Knoten erhalten bleiben
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)               # diese Zeile bei einem gerichteten Graphen weglassen

Dass man von der Knotenmenge ausgeht und nicht von den Kanten, hält isolierte Knoten im Graphen. Baut man das Dictionary nebenbei aus der Kantenliste auf, verschwindet jeder Knoten ohne Kanten stillschweigend, n ändert sich, und jede Berechnung, die durch n teilt, ist falsch.

10. Traversierung: Breitensuche und Tiefensuche

Fast jeder Graphenalgorithmus ist eine Traversierung mit zusätzlicher Buchführung. Es gibt zwei davon, sie unterscheiden sich in einer einzigen Datenstruktur, und diesen Unterschied zu verstehen, ist die wertvollste Stunde, die ein Anfänger in dieses Fach investieren kann. Beide beginnen bei einem Knoten, führen eine Sammlung entdeckter, aber noch nicht bearbeiteter Knoten und wiederholen: einen herausnehmen, seine Nachbarn ansehen, die neuen hinzufügen. Die Breitensuche nimmt sie in der Reihenfolge heraus, in der sie hineinkamen, mithilfe einer Warteschlange. Die Tiefensuche nimmt den zuletzt hinzugefügten heraus, mithilfe eines Stapels oder des Aufrufstapels einer rekursiven Funktion. Diese eine Entscheidung erzeugt zwei völlig verschiedene Formen der Erkundung.

Hier ist die Breitensuche vollständig. Sie liefert die Besuchsreihenfolge, den Abstand vom Start und den Baum der Elternknoten, mit dem sich die tatsächlichen Routen rekonstruieren lassen:

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    parent = {start: None}
    queue = deque([start])
    order = []
    while queue:
        u = queue.popleft()          # eine Warteschlange: first in, first out
        order.append(u)
        for v in graph[u]:
            if v not in dist:        # noch nicht entdeckt
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)
    return order, dist, parent

order, dist, parent = bfs(graph, 'A')
# order  ['A', 'B', 'C', 'D', 'E', 'F', 'G']
# dist   {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3, 'G': 4}

Die wichtige Eigenschaft steckt im Dictionary dist . Weil BFS eine ganze Schicht abschließt, bevor die nächste beginnt, hat sie beim ersten Erreichen eines Knotens die geringstmögliche Zahl von Kanten benutzt, also löst BFS das Kürzeste-Wege-Problem in ungewichteten Graphen in O(n + m). Zu Dijkstra zu greifen, wenn jede Kante gleich viel kostet, ist verschwendete Arbeit.

Die Tiefensuche ist dasselbe Gerüst, nur mit einem Stapel statt einer Warteschlange:

def dfs(graph, start):
    seen = set()
    order = []
    stack = [start]
    while stack:
        u = stack.pop()              # ein Stapel: last in, first out
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in reversed(graph[u]): # umgekehrt, damit der erste Nachbar zuerst drankommt
            if v not in seen:
                stack.append(v)
    return order

dfs(graph, 'A')   # ['A', 'B', 'C', 'E', 'D', 'F', 'G']

DFS liefert keine Abstände, und die nützliche Ausgabe ist die Reihenfolge, in der sie Knoten abschließt, nicht die, in der sie sie beginnt. Aus dieser Abschlussreihenfolge sind topologische Sortierung, Zyklenerkennung, starke Zusammenhangskomponenten und die Suche nach Brücken aufgebaut, im Anschluss an Tarjans Arbeit von 1972, die die Tiefensuche von einer Technik zu einem Werkzeugkasten machte.

Ein ausführlicherer Vergleich der beiden, einschließlich der Fehler, zu denen jede verleitet, steht in BFS vs DFS.

11. Die klassischen Probleme und ihre Algorithmen

Mit der Traversierung im Gepäck ist der Standardkatalog in Reichweite. Jedes dieser Probleme ist eine Frage, die man sich über reale Netzwerke tatsächlich stellt, und für jedes gibt es einen benannten Algorithmus.

Kürzeste Wege. Ohne Gewichte beantwortet BFS die Frage. Mit nicht negativen Gewichten legt der Dijkstra-Algorithmus, 1959 in einer dreiseitigen Notiz veröffentlicht, die Knoten in aufsteigender Reihenfolge ihres Abstands fest und läuft mit einer guten Prioritätswarteschlange in O(m + n log n) . Bei negativen Gewichten versagt Dijkstras zentrale Annahme, und man braucht Bellman-Ford, der jede Kante n-1 Mal relaxiert, in O(nm) , und als Zugabe negative Kreise erkennt. Für alle Paare zugleich erledigt das Floyd-Warshall in O(n3) mit drei verschachtelten Schleifen, und wenn man ein Ziel und eine vernünftige Schätzung der verbleibenden Entfernung hat, nutzt die A*-Suche diese, um nur einen Bruchteil des Graphen zu untersuchen. Der vollständige Entscheidungsbaum steht unter Algorithmen für kürzeste Wege.

Minimale Spannbäume. Finde die günstigste Kantenmenge, die einen gewichteten Graphen zusammenhängend hält. Der Kruskal-Algorithmus sortiert die Kanten und fügt jede hinzu, die keinen Kreis schließt, wobei er das mit einer Union-Find -Struktur in nahezu konstanter Zeit prüft; Prim lässt einen einzigen Baum nach außen wachsen und nimmt stets die günstigste Kante, die ihn verlässt. Beide sind gierig, beide sind beweisbar optimal, und beide laufen in O(m log n). Dieser Algorithmus steckt hinter dem kostenminimalen Verlegen von Kabeln und Glasfasern, und er taucht auch in Clustering-Verfahren auf.

Reihenfolge und Fluss. Für einen DAG von Abhängigkeiten liefert die topologische Sortierung eine Reihenfolge, in der jede Aufgabe nach dem kommt, wovon sie abhängt, in O(n + m), und sie scheitert genau dann, wenn ein Kreis existiert. Für Rohre mit Kapazitäten fragt der maximale Fluss, wie viel sich von einer Quelle zu einer Senke bewegen lässt; 1956 von Ford und Fulkerson formalisiert, modelliert er Verkehr, Bandbreite, Lieferketten und, über eine Standardreduktion, bipartites Matching. Siehe Netzwerkfluss, Max-Flow und Min-Cut.

Färbung. Beschrifte die Knoten so, dass keine zwei benachbarten dieselbe Beschriftung tragen, und verwende dabei so wenige Beschriftungen wie möglich. Diese Anzahl ist die chromatische Zahl, und sie modelliert Prüfungspläne, Frequenzzuteilung und Registerzuteilung. Anders als alles oben ist dieses Problem NP-schwer, und in der Praxis verlässt man sich auf Heuristiken. Siehe das Graphenfärbungsproblem.

Rundreisen. Ein Hamiltonkreis besucht jeden Knoten genau einmal, und das Problem des Handlungsreisenden fragt nach dem günstigsten. Es sieht aus wie eine kleine Variation von Eulers Frage aus dem Jahr 1736, die in linearer Zeit lösbar ist, und gehört doch zu den schwersten Problemen des Katalogs. Sein praktischer Verwandter, eine Fahrzeugflotte unter Kapazitätsgrenzen von einem Depot aus zu routen, ist das Tourenplanungsproblem.

12. Fünf Ergebnisse, die man beim Namen kennen sollte

Ein Einführungskurs ist teils eine Sammlung von Algorithmen und teils eine Sammlung von Ergebnissen, die prägen, wie man über die Objekte denkt. Das Handschlaglemma aus Abschnitt 4 ist das erste davon. Die folgenden fünf tauchen ebenso ständig auf, in Interviews, in Fachartikeln und im Gespräch, und jedes lässt sich in einem Satz formulieren.

Eulers Kriterium für das Durchlaufen aller Kanten (1736, von Hierholzer 1873 vervollständigt)

Ein zusammenhängender Graph besitzt genau dann einen geschlossenen Kantenzug, der jede Kante genau einmal benutzt, wenn jeder Knoten geraden Grad hat, und genau dann einen offenen, wenn genau zwei Knoten ungeraden Grad haben. Das ist die wertvolle Art von Satz: Er verwandelt eine Suche über einen riesigen Raum von Routen in eine Prüfung, die man durch Zählen erledigt, in linearer Zeit.

Eulers Polyederformel für planare Graphen (1758)

Zeichnen Sie einen zusammenhängenden planaren Graphen ohne Kreuzungen, und sei f die Anzahl der Flächen, einschließlich des unbeschränkten äußeren Gebiets. Dann gilt

n - m + f = 2

Das durchgehende Beispiel, gezeichnet wie in den Abbildungen, hat n = 7, m = 8 und drei Flächen: das Dreieck ABC, das Viereck BCED und das äußere Gebiet, und tatsächlich ist 7 - 8 + 3 = 2. Die Folgerung hat echten Biss: Jeder einfache planare Graph mit mindestens drei Knoten erfüllt m ≤ 3n - 6, planare Graphen sind also stets dünn besetzt, und K5 mit seinen 5 Knoten und 10 Kanten kann nicht planar sein, da 3n - 6 gleich 9 ist. Der Satz von Kuratowski aus dem Jahr 1930 vervollständigt das Bild: Ein Graph ist genau dann planar, wenn er keine Unterteilung von K5 oder K3,3enthält. Hopcroft und Tarjan zeigten 1974, dass sich Planarität in linearer Zeit testen lässt.

Der Vierfarbensatz (Appel und Haken, 1976)

Jeder planare Graph lässt sich mit höchstens vier Farben korrekt färben, keine Landkarte braucht also mehr als vier Farben, damit sich Länder mit gemeinsamer Grenze unterscheiden. Francis Guthrie stellte die Frage 1852, und sie widerstand 124 Jahre lang jedem Beweis. Das schließlich gefundene Argument reduzierte das Problem auf eine endliche Menge von Konfigurationen und prüfte diese per Computer, was eine echte philosophische Debatte darüber auslöste, was ein Beweis ist; 1997 wurde es von Robertson, Sanders, Seymour und Thomas vereinfacht und 2005 von Georges Gonthier in Coq formal verifiziert. Beachten Sie die Asymmetrie: Vier Farben reichen immer, aber zu entscheiden, ob drei reichen, ist NP-vollständig.

Satz von Kőnig (1931)

In einem bipartiten Graphen ist die Größe eines maximalen Matchings gleich der Größe einer minimalen Knotenüberdeckung. Ein Matching ist eine Menge von Kanten ohne gemeinsamen Endknoten, eine Art, Menschen Stellen zuzuordnen; eine Knotenüberdeckung ist eine Menge von Knoten, die jede Kante berührt. Zwei scheinbar unverbundene Optimierungsprobleme haben dieselbe Antwort, das ist die erste Dualität, der die meisten Studierenden begegnen, und sie macht maximales Matching in Polynomialzeit berechenbar. In allgemeinen Graphen gilt die Gleichheit nicht, und die minimale Knotenüberdeckung ist NP-schwer.

Das Max-Flow-Min-Cut-Theorem (Ford und Fulkerson, 1956)

In jedem Flussnetzwerk ist der maximale Fluss von der Quelle zur Senke gleich der Gesamtkapazität des kleinsten Schnitts, der sie trennt: Das Meiste, was man durchschieben kann, ist genau das, was der engste Engpass zulässt. Das ist wieder Dualität, in ihrer zitierfähigsten Form, die eine Maximierung über alle Flüsse in eine Minimierung über alle Schnitte verwandelt. Sie liegt Bildsegmentierung, Projektauswahl und Zuverlässigkeitsanalyse zugrunde, und der Satz von Kőnig fällt als Spezialfall daraus heraus.

13. Was leicht ist, was schwer ist und warum das wichtig ist

Das praktisch Wichtigste, was ein Anfänger über Graphen lernen kann, ist kein Algorithmus. Es ist die Tatsache, dass zwei Probleme fast gleich formuliert sein und doch auf entgegengesetzten Seiten einer enormen rechnerischen Kluft liegen können. Den kürzesten Pfad zwischen zwei Knoten zu finden, dauert auf einem Graphen mit Millionen von Knoten Millisekunden; den längsten einfachen Pfad zwischen denselben beiden zu finden, ist NP-schwer und jenseits einiger Dutzend Knoten aussichtslos. Zu entscheiden, ob ein Graph einen geschlossenen Kantenzug hat, der jede Kante einmal benutzt, ist eine Gradprüfung in linearer Zeit; zu entscheiden, ob er einen Kreis durch jeden Knoten einmal hat, ist NP-vollständig. Zu entscheiden, ob zwei Farben reichen, ist eine einzige BFS; zu entscheiden, ob drei reichen, ist NP-vollständig.

Die formale Aussage lautet, dass eine große Familie von Graphenproblemen NP-vollständigist, ein Begriff, den Cook 1971 einführte und dem Richard Karp 1972 den ersten umfangreichen Katalog gab. Seine berühmte Liste von 21 Problemen wird von Graphenproblemen dominiert: Clique, Knotenüberdeckung, Hamiltonkreis, chromatische Zahl, Feedback Arc Set und weitere. Für keines davon ist ein Polynomialzeitalgorithmus bekannt, und einer für irgendeines davon ergäbe einen für alle. Niemand erwartet, dass das geschieht.

Die praktische Konsequenz ist keine Verzweiflung, sondern eine andere Fragestellung. Landet ein Problem in der rechten Spalte, hört man auf, nach dem Optimum zu fragen, und wählt zwischen vier ehrlichen Strategien:

• Eine Näherung akzeptieren. Für das metrische TSP garantiert der Algorithmus von Christofides aus dem Jahr 1976 in Polynomialzeit eine Rundreise, die höchstens 1,5-mal so lang ist wie das Optimum.
• Eine Heuristik verwenden und sie messen. Lokale Suche wie 2-opt oder Simulated Annealing landet bei Tausenden von Städten regelmäßig wenige Prozent vom Optimum entfernt, ganz ohne Garantie.
• Die Struktur der eigenen Instanzen ausnutzen. Allgemein schwer heißt nicht schwer für Sie: Färbung ist auf chordalen Graphen leicht, viele Probleme sind auf Bäumen und auf Graphen mit kleiner Baumweite leicht, und Straßennetze haben eine Geometrie, die spezialisierte Routingalgorithmen rücksichtslos ausnutzen.
• Kleinere Instanzen exakt lösen. Löser für ganzzahlige Optimierung beweisen routinemäßig die Optimalität von TSP-Instanzen mit Tausenden von Städten. Exponentiell heißt nicht unmöglich, sondern dass die Obergrenze schnell erreicht ist.

Ein Vorbehalt: „NP-schwer“ beschreibt den schlimmsten Fall bei wachsender Eingabe, kein Urteil über Ihr konkretes Problem. Eine ausführlichere Behandlung der Kosten jedes Algorithmus steht unter Graphenalgorithmen und Komplexität.

14. Wo Graphen tatsächlich vorkommen

Die Behauptung, Graphentheorie sei überall, ist leicht aufgestellt und verdient einen Beleg. Hier ist, wo der Stoff dieses Artikels gerade jetzt arbeitet, auf dem Gerät, auf dem Sie das lesen.

Navigation. Jede Routing-App modelliert das Straßennetz als gewichteten gerichteten Graphen, Kreuzungen als Knoten und Straßenabschnitte als Bögen, gewichtet mit der erwarteten Fahrzeit. Die Anfrage ist ein kürzester Weg, und der Algorithmus ist ein technisch ausgefeilter Nachfahre von Dijkstra und A*, der vorberechnete Hierarchien nutzt, sodass eine kontinentale Route einige Tausend Knoten statt Dutzender Millionen berührt. Einbahnstraßen sind der Grund, warum der Graph gerichtet sein muss; der Live-Verkehr ist der Grund, warum sich die Gewichte minütlich ändern.

Suche und soziale Plattformen. Das Web ist ein gerichteter Graph aus Seiten und Links, und PageRank, 1998 von Brin und Page beschrieben, bewertet eine Seite nach der Wahrscheinlichkeit, dass ein zufälliger Surfer, der Links folgt, dort landet, was eine Eigenvektorberechnung auf der Adjazenzstruktur ist. Auf sozialen Plattformen sind Menschen Knoten und Beziehungen Kanten: Milgrams Briefstudie von 1967 brachte die populären „sechs Grade der Trennung“ hervor, und eine Analyse des gesamten Facebook-Graphen aus dem Jahr 2012 bezifferte den durchschnittlichen Abstand zwischen zwei Nutzern auf 4,74. Community-Erkennung, Freundesempfehlungen und Einflussschätzung sind allesamt Standardberechnungen auf Graphen, ausgeführt in großem Maßstab.

Softwareentwicklung. Build-Systeme, Paketmanager und Tabellenkalkulationen verwalten einen DAG und sortieren ihn topologisch. Die Versionsgeschichte ist ein DAG von Commits, und ein Merge ist eine Frage nach gemeinsamen Vorfahren. Compiler erstellen Kontrollflussgraphen für die Optimierung und Interferenzgraphen für die Registerzuteilung, wobei das Zuteilen von Registern buchstäblich Graphenfärbung ist, und die Eliminierung toten Codes ist eine Erreichbarkeitsanfrage. Siehe Graphentheorie in der Softwareentwicklung.

Logistik. Die Auslieferungsplanung ist das Tourenplanungsproblem, die Lagerplatzwahl ist Standortplanung, und Lieferketten sind Flussnetzwerke mit Kapazitäten. Hier misst sich der Unterschied zwischen einem guten und einem schlechten Algorithmus in Treibstoff und Lohnkosten, und das Fachgebiet, das sich damit befasst, ist das Operations Research.

Wissenschaft und maschinelles Lernen. Ein Molekül ist ein Graph aus Atomen und Bindungen, und die Suche in einer chemischen Datenbank ist Teilgraphisomorphie. Die Genomassemblierung rekonstruiert eine Sequenz, indem sie einen Eulerweg in einem De-Bruijn-Graphen findet, womit Eulers Kriterium von 1736 280 Jahre später seinen Unterhalt verdient. Spektrales Clustering partitioniert Daten mithilfe der Eigenvektoren einer Graph-Laplace-Matrix, und Graph Neural Networks verallgemeinern die Faltung auf unregelmäßige Strukturen, indem sie Nachrichten entlang von Kanten weiterreichen. Stromnetze und Telekommunikationsnetze werden auf Brücken und Schnittknoten untersucht, weil dort Kaskadenausfälle beginnen. Einen breiteren Überblick gibt es unter Anwendungen der Graphentheorie.

15. Fehler, die Anfänger zuverlässig machen

Das sind die Fehler, die in studentischem Code, in Interviews und in Produktionsbugs immer wieder auftauchen. Jeder davon lässt sich mühelos vermeiden, sobald man ihn einmal beim Namen gesehen hat.

• Isolierte Knoten verlieren. Baut man den Graphen aus einer Kantenliste auf, taucht jeder Knoten ohne Kanten nie auf. Die Ordnung n ändert sich stillschweigend, Durchschnitte sind falsch, und die Zahl der Komponenten ist zu klein. Bauen Sie zuerst die Knotenmenge auf.
• Bei BFS zu spät als besucht markieren. Markieren Sie einen Knoten, wenn Sie ihn in die Warteschlange einreihen, nicht wenn Sie ihn entnehmen. Beim Entnehmen zu markieren, lässt denselben Knoten einmal pro inzidenter Kante in die Warteschlange, was aus einem linearen Algorithmus ein Speicherproblem macht.
• BFS auf einem gewichteten Graphen ausführen. BFS minimiert die Anzahl der Kanten, nicht ihr Gesamtgewicht. In einem Graphen, in dem eine Route mit zwei Kanten 100 kostet und eine mit fünf Kanten 5, liefert BFS selbstbewusst die teure. Gewichtete Graphen brauchen Dijkstra.
• Dijkstra mit negativen Gewichten ausführen. Dijkstra nimmt an, dass für einen festgelegten Knoten später keine günstigere Route mehr auftauchen kann. Eine negative Kante bricht diese Annahme, und die Ausgabe ist stillschweigend falsch statt ein Fehler. Verwenden Sie Bellman-Ford.
• Pfadlänge in Knoten zählen. Die Länge ist die Anzahl der Kanten, ein Pfad durch fünf Knoten hat also Länge 4. Das ist die Quelle eines großen Teils der Off-by-one-Fehler in Code für kürzeste Wege.
• Ignorieren, zu welcher Familie der Graph gehört. Ein Algorithmus, der auf ungerichteten Graphen korrekt ist, kann auf gerichteten stillschweigend falsch sein, und ein für einfache Graphen bewiesenes Ergebnis kann auf einem Multigraphen scheitern. Prüfen Sie die Familie, bevor Sie zum Algorithmus greifen.
• Annehmen, dass der Graph zusammenhängend ist. Reale Daten kommen in Stücken an. Prüfen Sie die Zahl der Komponenten, bevor Sie irgendeinem Abstand, Durchmesser oder Durchschnitt trauen.
• Bei DFS zu tief rekursieren. Eine rekursive DFS auf einem Pfad mit einer Million Knoten braucht eine Million Stack-Frames. Schreiben Sie die iterative Version, wenn die Eingabe groß sein kann.
• In einem ungerichteten Graphen nur eine Richtung hinzufügen. Eine ungerichtete Kante muss in beiden Adjazenzlisten auftauchen. Wer das zweite append weglässt, erhält einen Graphen, der in einer Zeichnung richtig aussieht und sich bei jeder Traversierung wie ein Digraph verhält.
• Der Zeichnung glauben. Zwei sich kreuzende Kanten in einem Bild bedeuten nichts. Nur die Mengen zählen, und deshalb ist „Ist dieser Graph planar?“ eine echte Frage und nichts, was man durch Blinzeln auf ein Diagramm klärt.
• Annehmen, dass n - 1 Kanten einen Baum bedeuten. Das gilt nur zusammen mit Zusammenhang oder mit Kreisfreiheit. Ein Dreieck plus ein isolierter Knoten hat 4 Knoten und 3 Kanten und ist kein Baum.

16. Wie es weitergeht

Der sinnvolle nächste Schritt ist, einen Graphen zu bauen und etwas darauf laufen zu lassen, statt weitere Definitionen zu lesen. Geben Sie das durchgehende Beispiel in den interaktiven Visualisiererein, starten Sie die Breitensuche bei A und beobachten Sie, wie sich die Schichten füllen, und starten Sie dann die Tiefensuche vom selben Knoten aus und vergleichen Sie die Reihenfolge. Neunzig Sekunden davon leisten, was keine noch so lange Prosa leistet.

Danach ist die natürliche Abfolge die Reihenfolge dieses Artikels: Vokabular, Traversierung, gewichtete kürzeste Wege, Spannbäume, dann die schwereren Probleme. Der Graphentheorie-Lernpfad legt diesen Weg mit einem Zeitplan dar, und die strukturierten Lektionen folgen ihm interaktiv. Für technische Interviews behandelt der Leitfaden zu Graphentheorie in Programmier-Interviews die Muster, die tatsächlich vorkommen, ergänzt durch den Algorithmen-Spickzettel.

Zu Lehrbüchern: Wests Introduction to Graph Theory ist der Standard-Grundkurs in Buchform, Diestels Graph Theory ist das Referenzwerk für Fortgeschrittene und die Quelle der Definition aus Abschnitt 2, und die Graphenkapitel von Cormen, Leiserson, Rivest und Stein sind nach wie vor die klarste Darstellung der Implementierungen. Ein ausführlicherer Vergleich, einschließlich Kursen und Videoreihen, steht unter den besten Ressourcen zum Lernen der Graphentheorie.

17. Glossar

Jeder oben verwendete Begriff an einem Ort.

19. Quellen

Die Definitionen, Sätze, Jahreszahlen und Komplexitätsschranken oben stammen aus diesen Quellen, in chronologischer Reihenfolge aufgeführt.

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (erschienen 1741), 128 bis 140. Die Arbeit über die Königsberger Brücken.
2. Euler, L. (1758). "Elementa doctrinae solidorum." Novi Commentarii Academiae Scientiarum Petropolitanae 4, 109 bis 140. Die Polyederformel hinter n - m + f = 2.
3. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird." Annalen der Physik 148(12), 497 bis 508.
4. Hierholzer, C. (1873). "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6(1), 30 bis 32.
5. Sylvester, J. J. (1878). "Chemistry and Algebra." Nature 17, 284. Die erste moderne Verwendung des Wortes „Graph“.
6. Cayley, A. (1889). "A theorem on trees." Quarterly Journal of Pure and Applied Mathematics 23, 376 bis 378.
7. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15, 271 bis 283.
8. König, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38, 116 bis 119.
9. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft.
10. Ford, L. R. und Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics 8, 399 bis 404.
11. Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical Society 7(1), 48 bis 50.
12. Prim, R. C. (1957). "Shortest connection networks and some generalizations." Bell System Technical Journal 36(6), 1389 bis 1401.
13. Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269 bis 271.
14. Floyd, R. W. (1962). "Algorithm 97: Shortest path." Communications of the ACM 5(6), 345.
15. Held, M. und Karp, R. M. (1962). "A dynamic programming approach to sequencing problems." Journal of the Society for Industrial and Applied Mathematics 10(1), 196 bis 210.
16. Milgram, S. (1967). "The small world problem." Psychology Today 2(1), 60 bis 67.
17. Cook, S. A. (1971). "The complexity of theorem-proving procedures." Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151 bis 158.
18. Karp, R. M. (1972). "Reducibility among combinatorial problems." In Complexity of Computer Computations, 85 bis 103. New York: Plenum Press.
19. Tarjan, R. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing 1(2), 146 bis 160.
20. Hopcroft, J. und Tarjan, R. (1974). "Efficient planarity testing." Journal of the ACM 21(4), 549 bis 568.
21. Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388, Carnegie Mellon University.
22. Appel, K. und Haken, W. (1977). "Every planar map is four colorable." Illinois Journal of Mathematics 21(3). Teil I, 429 bis 490; Teil II, mit J. Koch, 491 bis 567.
23. Fredman, M. L. und Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms." Journal of the ACM 34(3), 596 bis 615.
24. 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.
25. West, D. B. (2001). Introduction to Graph Theory, 2. Auflage. Upper Saddle River: Prentice Hall.
26. Bondy, J. A. und Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
27. Gonthier, G. (2008). "Formal proof: the four-color theorem." Notices of the American Mathematical Society 55(11), 1382 bis 1393.
28. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage. Cambridge, Massachusetts: MIT Press.
29. Backstrom, L., Boldi, P., Rosa, M., Ugander, J. und Vigna, S. (2012). "Four degrees of separation." Proceedings of the 4th Annual ACM Web Science Conference, 33 bis 42.
30. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer. Quelle der in Abschnitt 2 zitierten Definition.