Einfache Graphen und Multigraphen erklärt

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Drei Definitionen, zwei Erweiterungen

Zwei Dinge kann eine Menge ungeordneter Paare nicht ausdrücken: eine Kante, die einen Knoten mit sich selbst verbindet, und zwei verschiedene Kanten, die dasselbe Paar verbinden. Ob man sie zulässt, ergibt drei verschiedene Objekte, und die Namen sollte man genau nehmen, weil Sätze immer über bestimmte dieser Objekte formuliert werden.

Der einfache Graph ist in der meisten Literatur der Standard, und seine Definition ist die aus dem Leitfaden zu Knoten und Kanten:

G = (V, E)      mit   E ⊆ [V]²      jede Kante ist eine 2-elementige Teilmenge von V

Da E eine Menge 2-elementiger Teilmengen ist, ist {v, v} nicht zulässig (es hat nur ein Element), und dasselbe Paar kann nicht zweimal vorkommen (eine Menge enthält jedes Element nur einmal). Beide Einschränkungen sind Folgen der Notation, nicht Entscheidungen, die jemand getroffen hat.

Um sie aufzuheben, braucht man einen anderen Formalismus. Bondy und Murtys Graph Theory gibt Kanten eine eigene Identität und fügt eine Funktion hinzu, die angibt, welches Paar jede Kante verbindet:

G = (V, E, ψ)      mit   ψ: E → ungeordnete Paare von (nicht notwendig verschiedenen) Knoten

Nun können e1 und e2 verschiedene Elemente von E sein mit ψ(e1) = ψ(e2) = {u, v}, was ein Paar paralleler Kanten ergibt, und ψ(e) = {v, v} ist eine Schleife. Diestel gelangt mit zwei Abbildungen, die jeder Kante ihre Enden zuordnen, an dieselbe Stelle, und West mit einer Relation, die jeder Kante ihre Endpunkte zuordnet. Der Formalismus unterscheidet sich, der Inhalt nicht.

Zwei Warnungen zum Vokabular selbst, weil es beim Lesen von Fachartikeln echte Verwirrung stiftet:

• „Multigraph“ wird nicht einheitlich verwendet. Manche Autoren erlauben Schleifen in einem Multigraphen, andere reservieren das für „Pseudograph“, und einige verwenden „Multigraph“ für jeden beliebigen Graphen. Prüfen Sie die Definition der Quelle, bevor Sie einen ihrer Sätze zitieren.
• „Graph“ bedeutet meist „einfacher Graph“. Die meisten Lehrbücher sagen das einmal in Kapitel eins und wiederholen es dann nie. Ein Resultat über „Graphen“ hat oft eine unausgesprochene Einfachheitsannahme, und Abschnitt 5 zeigt, wie schwer manche davon ohne sie scheitern.

2. Die Graphentheorie wurde auf einem Multigraphen gegründet

Das ist kein Randfall, der nachträglich angeschraubt wurde. Das Problem, mit dem das Fach begann, ist ein Multigraph, und es ist nicht mehr dasselbe Problem, wenn man es vereinfacht.

Eulers Arbeit von 1736 über die Brücken von Königsberg modelliert vier Landmassen, die durch sieben Brücken verbunden sind. Zwei Brücken verbinden das Nordufer mit der Insel, zwei weitere das Südufer mit der Insel. Das sind parallele Kanten, und kein einfacher Graph kann sie aufnehmen.

Eulers Kriterium betrifft die Parität der Grade, und die parallelen Brücken sind es, die die Grade dorthin bringen, wo sie sind:

Königsberger Multigraph        7 Kanten    Grade 3, 5, 3, 3    vier ungerade  → kein Eulerweg
Zugehöriger einfacher Graph    5 Kanten    Grade 2, 3, 2, 3    zwei ungerade  → ein Eulerweg existiert

Löschen Sie die Duplikate, und die Antwort kippt. Die Vielfachheit ist keine Dekoration am Modell, sie ist das Modell, und das historische Detail in der Geschichte der Graphentheorie ist untrennbar mit dem Formalismus verbunden. Wer die sieben Brücken in eine Datenstruktur lädt, die Kanten stillschweigend dedupliziert, wird zu dem Schluss kommen, Euler habe sich geirrt.

3. Was eine Schleife mit dem Grad macht

Der Grad zählt Kantenenden , die an einem Knoten zusammentreffen, nicht Kanten. Eine Schleife hat zwei Enden, und beide landen am selben Knoten, also gilt:

Eine Schleife an v trägt 2 zu deg(v) bei. Parallele Kanten tragen jeweils 1 bei, genau wie getrennte Kanten.

Diese Konvention ist erzwungen, nicht gewählt. Das Handschlaglemma zählt die Paare (Knoten, Kantenende daran) auf zwei Arten, und jede Kante, auch eine Schleife, hat genau zwei Enden, also gilt ∑ deg(v) = 2m für Pseudographen unverändert. Gibt man einer Schleife den Grad 1, bricht der älteste Satz des Fachs sofort.

Einige Folgerungen, die man im Kopf haben sollte:

• Ein Knoten mit einer Schleife und sonst keinen Kanten hat den Grad 2, nicht 0, und ist nicht isoliert.
• Die Anzahl der Knoten mit ungeradem Grad ist weiterhin gerade, da der Beweis nur ∑ deg(v) = 2m verwendet.
• In einem einfachen Graphen gilt deg(v) = |N(v)|, die Größe der Nachbarschaft. In einem Multigraphen gilt diese Identität nicht: Drei parallele Kanten zu einem Nachbarn ergeben Grad 3 und einen Nachbarn. Code, der den Grad als Länge einer deduplizierten Nachbarmenge berechnet, berechnet die falsche Zahl.

4. Was Vielfachheit ändert und was nicht

Die nützliche Frage ist nicht „Ist mein Graph einfach?“, sondern „Hängt die Eigenschaft, die ich berechne, von der Vielfachheit ab?“. Die Antworten teilen sich klar auf, und die Aufteilung ist nicht offensichtlich.

Drei dieser Zeilen verdienen eine ausführliche Begründung.

Färbung ignoriert parallele Kanten, scheitert aber an Schleifen. Eine echte Färbung verlangt, dass die Enden jeder Kante verschiedene Farben erhalten. Eine zweite Kopie von {u, v} wiederholt eine Bedingung, die schon da ist, also sind die Menge der echten Färbungen und damit die chromatische Zahl und das chromatische Polynom genau die des zugrunde liegenden einfachen Graphen. Eine Schleife verlangt c(v) ≠ c(v), was nichts erfüllt, also hat ein Pseudograph mit einer Schleife überhaupt keine echte Färbung, und sein chromatisches Polynom ist identisch null. Deshalb wird die Graphenfärbung fast immer für schleifenlose Graphen formuliert.

Die Anzahl der Spannbäume hängt von der Vielfachheit ab. Zwei Knoten, die durch eine einzelne Kante verbunden sind, haben einen Spannbaum; verbunden durch zwei parallele Kanten haben sie zwei, weil die Wahl jeder Kante einen anderen Baum ergibt. Kirchhoffs Matrix-Baum-Satz von 1847 zählt sie aus der Laplace-Matrix, und er ist genau deshalb für Multigraphen formuliert, weil die Vielfachheiten als Anzahlen außerhalb der Diagonale in die Matrix eingehen. Elektrische Netzwerke, bei denen Kirchhoff auf das Problem stieß, haben regelmäßig parallel geschaltete Bauteile.

Schnitte und Flüsse hängen von der Vielfachheit ab. Die minimale Anzahl von Kanten, deren Entfernen u von v trennt, ist 1, wenn eine einzelne Kante sie verbindet, und 2, wenn es zwei sind. Da maximaler Fluss gleich minimalem Schnitt gilt, gilt dasselbe für den Fluss: k parallele Kanten mit Einheitskapazität transportieren k Einheiten. Genau deshalb ist ein Multigraph mit Einheitskapazitäten das natürliche ungewichtete Modell eines Flussnetzwerks.

5. Jede Schranke für einfache Graphen verliert ihre Gültigkeit

Ein großer Teil der Standardresultate trägt eine unausgesprochene Einfachheitsannahme, und ohne sie werden sie nicht allmählich schlechter. Sie scheitern komplett.

Die beiden Zeilen, die überleben, verdienen ebenso Beachtung wie die, die scheitern. Das Handschlaglemma und Eulers Polyederformel werden beide durch Zählen von Inzidenzen bewiesen, und Zählargumente kümmert es nicht, ob zwei Kanten zufällig dasselbe Paar verbinden. Die Schranken, die scheitern, sind die, die durch Wahl verschiedener Knotenpaare bewiesen werden, und genau diesen Schritt macht ein Multigraph ungültig.

Die praktische Fassung dieses Abschnitts: Wenn Sie eine Schranke nachschlagen, prüfen Sie, ob ihr Beweis Inzidenzen oder Paare zählt. Die erste Art überträgt sich auf Multigraphen, die zweite nicht.

6. Speicherung: wo die Adjazenzmatrix an ihre Grenzen stößt

Die drei Standarddarstellungen verschlechtern sich sehr unterschiedlich, und die Unterschiede entscheiden, welche man verwendet.

Die Adjazenzmatrix ist keine 0/1-Matrix mehr. Die natürliche Erweiterung speichert die Anzahl der Kanten zwischen jedem Paar, der Eintrag (u, v) wird also zu einer Anzahl, und eine Schleife setzt nach Konvention 2 auf die Diagonale, damit die Zeilensummen weiterhin die Grade liefern. Das funktioniert, hat aber eine fatale Einschränkung für echte Daten: Eine Anzahl kann keine Information pro Kante tragen. Wenn Ihre drei parallelen Flüge jeweils einen anderen Preis haben, hat eine Matrix aus Anzahlen keinen Platz dafür.

einfach        A[u][v] ∈ {0, 1}
Multigraph     A[u][v] = Anzahl der Kanten zwischen u und v
Pseudograph    A[v][v] = 2 × (Anzahl der Schleifen an v)      damit Zeilensummen Grade sind

Die Adjazenzliste behält Duplikate. Die Liste von u enthält v einfach so oft, wie es Kanten zwischen ihnen gibt. Der Durchlaufcode bleibt unverändert, und BFS oder DFS betrachten denselben Nachbarn mehrmals, was harmlos ist, solange die Besucht-Prüfung auf Knoten erfolgt.

Die Kantenliste wird zum natürlichen Format. Das ist die Darstellung, die wirklich zur Mathematik passt: Jede Kante ist ein Datensatz mit eigener Identität, parallele Kanten sind also einfach verschiedene Datensätze, und Attribute pro Kante haben einen Platz. Das ist die Definition über die Inzidenzfunktion aus Abschnitt 1 , als Datenstruktur ausgedrückt.

Daraus folgt ein Entwurfsgrundsatz, und er ist das Nützlichste, was man aus diesem Abschnitt mitnehmen kann:

In einem Multigraphen brauchen Kanten Identitäten. Ein Paar von Endpunkten identifiziert keine Kante mehr, also muss alles, was sich auf eine Kante bezieht, ob Matching, Spannbaum, Fluss oder Löschung, auf eine Kanten-ID verweisen und nicht auf (u, v).

Fast jeder Multigraph-Bug geht auf diesen einen Satz zurück. Wer einen Spannbaum als Menge von Knotenpaaren speichert oder eine Menge besuchter Kanten mit dem Schlüssel (u, v) führt, vermischt stillschweigend parallele Kanten und erhält Antworten, die auf eine Weise falsch sind, die kein Typprüfer bemerkt.

7. Welche Algorithmen das betrifft

Die meisten durchlaufartigen Algorithmen sind gegenüber der Vielfachheit gleichgültig, weil sie Knoten markieren. Diejenigen, die Kanten markieren oder auswählen, brauchen Aufmerksamkeit.

Die Karger-Zeile überrascht viele, und sie verdient eine vollständige Erklärung, weil sie den üblichen Instinkt umkehrt. Kargers randomisierter Algorithmus für den minimalen Schnitt kontrahiert wiederholt eine gleichverteilt zufällig gewählte Kante und verschmilzt ihre beiden Endpunkte zu einem Knoten. Die Kontraktion macht aus zwei Kanten, die auf die beiden verschmolzenen Knoten zeigten, zwei parallele Kanten zum neuen Knoten, und die Wahrscheinlichkeitsanalyse des Algorithmus hängt davon ab, jede Kopie zu behalten, weil die Chance, eine Kante zu kontrahieren, proportional zur Anzahl ihrer Kopien ist. Vereinfacht man den Zwischengraphen, ist der Algorithmus nicht mehr korrekt. Dasselbe gilt für den Kontraktionsschritt in Borůvkas Spannbaum-Algorithmus.

8. Wann ein Multigraph nicht optional ist

Multigraphen sind keine Kuriosität, die man wegnormalisieren sollte. Sie sind das ehrliche Modell, wann immer zwei Objekte mehr als einmal in Beziehung stehen können und die einzelnen Beziehungen wichtig sind:

• Verkehrsnetze. Zwei Städte, die durch drei verschiedene Flüge verbunden sind, oder eine Straßen- und eine Bahnverbindung zwischen demselben Paar. Jede hat eigene Dauer, eigenen Preis und eigene Kapazität.
• Elektrische Schaltungen. Parallel geschaltete Bauteile zwischen denselben zwei Knoten, genau das Umfeld, in dem Kirchhoff 1847 den Matrix-Baum-Satz entwickelte.
• Transaktions- und Zahlungsgraphen. Zwei Konten können viele Male miteinander Geschäfte machen; das zu einer Kante zusammenzufassen verliert Beträge, Zeitstempel und die Anzahl selbst, die meist genau das gesuchte Signal ist.
• Chemische Reaktions- und Molekülgraphen. Doppel- und Dreifachbindungen sind im klassischen Graphenmodell eines Moleküls parallele Kanten.
• Wissensgraphen und RDF. Zwei Entitäten, die durch mehrere verschiedene Prädikate verbunden sind. Deshalb werden solche Daten meist als Tripel gespeichert, also als Kantenliste mit einer Beschriftung pro Kante.
• Alles, was durch Kontraktion entsteht. Kargers Algorithmus, Borůvkas Algorithmus und die Verdichtungsschritte in vielen Approximationsalgorithmen erzeugen während des Laufs parallele Kanten, ganz gleich, wie die Eingabe aussah.
• Euler-Routenprobleme. Straßenreinigung und Postrouten müssen jede physische Straße befahren, und zwei Straßen zwischen denselben Kreuzungen sind zwei Pflichten.

9. Vereinfachen und was es kostet

Einen Multigraphen in einen einfachen Graphen umzuwandeln ist oft der richtige Schritt, und es ist nur dann gefahrlos, wenn Sie wissen, welche der Eigenschaften aus Abschnitt 4 Sie gleich verändern. Es gibt drei Standardverfahren, und sie beantworten verschiedene Fragen:

Beachten Sie, dass die zweite und die dritte Regel unvereinbar sind: Summieren ist für Kapazitäten richtig und für Distanzen falsch, das Minimum ist für Distanzen richtig und für Kapazitäten falsch. Welche gilt, hängt davon ab, wie sich Gewichte entlang eines Weges verknüpfen, und das ist das Thema des begleitenden Leitfadens zu gewichteten und ungewichteten Graphen. Wer das falsche Zusammenfassen wählt, beantwortet stillschweigend eine andere Frage, und der Graph sieht hinterher völlig vernünftig aus.

Eine vierte Möglichkeit ist oft besser als alle drei: Behalten Sie den Multigraphen und lassen Sie den Algorithmus damit umgehen. BFS, DFS, Dijkstra, Kruskal und Prim laufen alle unverändert korrekt auf Multigraphen, also bringt Vereinfachen oft nichts und kostet Information.

10. Gerichtete Multigraphen

Alles oben Gesagte überträgt sich auf gerichtete Graphen, mit einer zusätzlichen Unterscheidung, die man benennen sollte. In einem Digraphen sind die Bögen (u, v) und (v, u) bereits verschiedene Objekte, und das ist keine Vielfachheit, sondern Richtung: Dieses Paar ist ein Digon, und ein gewöhnlicher Digraph darf ohne Erweiterung seiner Definition eines enthalten. Viele Digraphen enthalten gar keins: Ein DAG nie. Vielfachheit bedeutet im gerichteten Fall zwei oder mehr Bögen mit demselben Anfangsknoten und demselben Endknoten, was wieder eine Definition im Stil der Inzidenzfunktion braucht, wie in Bang-Jensen und Gutins Digraphs.

Die praktischen Folgen übertragen sich direkt: Eingangs- und Ausgangsgrad zählen Bögen statt verschiedener Nachbarn, eine gerichtete Schleife erhöht beide um 1, und die Euler-Bedingungen für einen gerichteten Multigraphen vergleichen weiterhin an jedem Knoten Eingangs- mit Ausgangsgrad.

11. Häufige Fehler

• Einen Multigraphen in eine deduplizierende Struktur laden. Ein Set von Paaren, eine boolesche Adjazenzmatrix oder eine Unique-Constraint in der Datenbank auf (u, v) verwerfen alle stillschweigend parallele Kanten. Der Graph sieht dann gut aus, und jede Zählung ist falsch.
• Kanten über ihre Endpunkte identifizieren. In einem Multigraphen bezeichnet (u, v) eine Menge von Kanten, nicht eine einzige. Matchings, Spannbäume, Flüsse und Mengen besuchter Kanten müssen Kanten-IDs als Schlüssel verwenden.
• Den Grad als Anzahl der Nachbarn berechnen. Richtig in einem einfachen Graphen, falsch, sobald eine Kante doppelt vorkommt oder eine Schleife auftaucht.
• Einer Schleife den Grad 1 geben. Sie trägt 2 bei, und das Handschlaglemma hängt davon ab.
• Die Schranke m ≤ n(n-1)/2 anwenden. Diese Schranke und alles daraus Abgeleitete, einschließlich Überlegungen zu dünn und dicht, braucht Einfachheit.
• Vor einer Euler-, Schnitt- oder Flussberechnung vereinfachen. Alle drei hängen von der Vielfachheit ab, wie Königsberg am Gründungsbeispiel des Fachs zeigt.
• Innerhalb eines Kontraktionsalgorithmus deduplizieren. Kargers und Borůvkas Algorithmen erzeugen parallele Kanten absichtlich und brauchen sie.
• Annehmen, eine Bibliothek tue, was man erwartet. Graphenbibliotheken unterscheiden sich darin, ob das Hinzufügen einer bestehenden Kante ein Duplikat erzeugt, ignoriert wird oder einen Fehler auslöst. Prüfen Sie es einmal in einem Test.

12. Glossar

14. Quellen

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

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (erschienen 1741), 128 bis 140. Die Königsberger Brücken, als Multigraph modelliert.
2. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik 148(12), 497 bis 508. Der Matrix-Baum-Satz, entwickelt an elektrischen Netzwerken mit parallelen Bauteilen.
3. Harary, F. (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley. Unterscheidet Graphen, Multigraphen und Pseudographen.
4. Karger, D. R. (1993). "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-cut Algorithm." Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 21 bis 30. Der Kontraktionsalgorithmus, der während des Laufs parallele Kanten erzeugt.
5. Karger, D. R. und Stein, C. (1996). "A New Approach to the Minimum Cut Problem." Journal of the ACM 43(4), 601 bis 640.
6. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. New York: Springer.
7. West, D. B. (2001). Introduction to Graph Theory, 2. Auflage. Upper Saddle River: Prentice Hall. Definiert einen Graphen über eine Knotenmenge, eine Kantenmenge und eine Endpunktrelation, die Schleifen und parallele Kanten zulässt.
8. Bondy, J. A. und Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer. Quelle der Definition über die Inzidenzfunktion in Abschnitt 1.
9. Bang-Jensen, J. und Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2. Auflage. London: Springer. Gerichtete Multigraphen.
10. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage. Cambridge, Massachusetts: MIT Press.
11. Wilson, R. J. (2010). Introduction to Graph Theory, 5. Auflage. Harlow: Prentice Hall. Entwickelt Multigraphen ab dem ersten Kapitel parallel zu einfachen Graphen.
12. Chartrand, G., Lesniak, L. und Zhang, P. (2015). Graphs & Digraphs, 6. Auflage. Boca Raton: CRC Press.
13. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer. Quelle der Definition einfacher Graphen und der Multigraph-Formulierung mit zwei Endabbildungen.