Gewichtete und ungewichtete Graphen erklärt

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Ein Gewicht ist eine Funktion, kein Teil des Graphen

Ein Graph ist ein Paar von Mengen, G = (V, E), und nichts in dieser Definition erwähnt Zahlen. Entfernungen, Kosten, Kapazitäten und Dauern kommen von außen, als eigene Funktion auf derselben Kantenmenge:

G = (V, E)                    der Graph: welche Paare verbunden sind
w: E → ℝ                    die Gewichtsfunktion: was jede Verbindung kostet

Die Standardwerke trennen das bewusst. Bondy und Murty definieren einen gewichteten Graphen als Graphen zusammen mit einer Zuordnung einer reellen Zahl zu jeder Kante und definieren dann das Gewicht eines Teilgraphen als Summe seiner Kantengewichte, und genau das minimieren ein kürzester Weg oder ein minimaler Spannbaum. Diestel behandelt Gewichte ebenso, als zusätzliche Daten über einem unveränderten kombinatorischen Objekt.

Die Funktion w außerhalb des Graphen zu halten, ist keine Pedanterie, es bringt drei Dinge:

• Ein Graph kann mehrere Kostenmodelle tragen. Ein Straßennetz ist ein einziger Graph G mit drei Funktionen darauf: Kilometer, Minuten, Liter Kraftstoff. Wer die Funktion austauscht, ändert jede Antwort, ohne einen Knoten oder eine Kante anzurühren.
• Bedingungen hängen an der Funktion, nicht an der Struktur. „Dijkstra braucht nichtnegative Gewichte“ ist eine Aussage über w. Dem Graphen ist das gleichgültig.
• Strukturelle Resultate bleiben bestehen. Zusammenhang, Planarität, Bipartitheit, Gradfolgen und das Handschlaglemma sind Eigenschaften von (V, E) allein, deshalb kann das Hinzufügen von Gewichten keine davon ändern.

Ein ungewichteter Graph ist dann einfach ein Graph ohne eine solche Funktion, und der nächste Abschnitt zeigt, dass das dasselbe ist, wie die langweiligste Funktion überhaupt anzugeben.

2. Ungewichtet heißt: Jedes Gewicht ist 1

Am klarsten lassen sich beide Fälle zusammendenken, wenn man „ungewichtet“ nicht als Fehlen von Gewichten behandelt, sondern als eine bestimmte Wahl von Gewichten:

Ein ungewichteter Graph ist ein gewichteter Graph mit w(e) = 1 für jede Kante. Das Gewicht eines Weges ist dann seine Kantenzahl, also bedeutet „kürzester Weg“ „wenigste Kanten“.

Alles folgt aus dieser einen Ersetzung. Die Breitensuche, die den Weg mit den wenigsten Kanten findet, ist genau das, wozu der Dijkstra-Algorithmus entartet, wenn jedes Gewicht 1 ist: Die Prioritätswarteschlange muss nie etwas umordnen, weil die Distanzen ohnehin in nicht fallender ganzzahliger Reihenfolge herauskommen, und eine einfache FIFO-Warteschlange erledigt dieselbe Aufgabe in O(n + m). Edward Moores Arbeit „The shortest path through a maze“ von 1959 stellte und löste genau dieses Problem mit Einheitsgewichten und gilt meist als Ursprung des Algorithmus.

Die Ersetzung funktioniert auch in die andere Richtung, und dort zeigt sich, was Gewichte kosten. Geben Sie demselben Graphen beliebige positive Gewichte, und die FIFO-Warteschlange funktioniert nicht mehr, weil ein Weg mit mehr Kanten jetzt billiger sein kann. Sie brauchen eine Prioritätswarteschlange, und die Laufzeit steigt von O(n + m) auf O(m log n) mit einem binären Heap oder O(m + n log n) mit dem Fibonacci-Heap von Fredman und Tarjan (1987).

3. Der kürzeste Weg ist nicht der kürzeste Weg

Hier ist die ganze Unterscheidung in einem Bild. Dieselben fünf Knoten, dieselben fünf Kanten und dieselbe Frage liefern zwei verschiedene Antworten, je nachdem, ob die Zahlen da sind.

Ausgeschrieben lautet der Graph

V = {A, B, C, D, E}
E = { {A,B}, {B,C}, {C,D}, {A,D}, {D,E} }
w =    1       1       1       7       2

und die beiden Fragen haben diese Antworten:

Beachten Sie, dass die gewichtete Antwort in beiden Zeilen mehr Kanten verwendet. Das ist der Normalfall und kein konstruierter: Ein Umweg über die Autobahn hat mehr Kreuzungen und braucht weniger Minuten. Eine Breitensuche auf einem gewichteten Graphen liefert keine Näherung, sondern die Antwort auf eine andere Frage, und die Lücke zwischen beiden ist unbeschränkt. Erhöhen Sie das Gewicht von {A, D} auf eine Million, und die Breitensuche liefert die Kante trotzdem.

4. Was ein Gewicht bedeutet: drei Arten der Verknüpfung

„Gewichteter Graph“ ist ein Behälter, keine Bedeutung. Bevor Sie einen Algorithmus wählen, müssen Sie eine vorgelagerte Frage beantworten: Wie verknüpfen sich die Gewichte entlang eines Weges zu dem Wert, der Sie interessiert? Es gibt drei übliche Antworten, und sie führen zu drei verschiedenen Problemen.

Der multiplikative Trick verdient eine genauere Erklärung, weil er überall vorkommt, vom Routing bis zur Dekodierung natürlicher Sprache. Ein Produkt von Wahrscheinlichkeiten entlang eines Weges zu maximieren ist dasselbe, wie die Summe ihrer negativen Logarithmen zu minimieren, da -log streng monoton fallend ist und Produkte in Summen verwandelt. Da jede Wahrscheinlichkeit höchstens 1 ist, ist jedes -log w nichtnegativ, sodass Dijkstra direkt anwendbar ist und kein spezieller Algorithmus nötig ist.

Es gibt noch eine Unterscheidung, die mehr Modellierungsfehler verursacht als alles oben Genannte, und sie hat mit Arithmetik gar nichts zu tun:

Bedeutet eine größere Zahl näher oder weiter weg? In einem Distanzgraphen ist ein großes Gewicht schlecht, und man minimiert. In einem Ähnlichkeitsgraphen ist ein großes Gewicht gut, und man maximiert. Beides ist gegensätzlich, und das Dateiformat verrät Ihnen nicht, welches Sie vor sich haben.

Korrelationsnetzwerke, Mitkaufgraphen und Ähnlichkeitsgraphen aus Embeddings sind alle nach Ähnlichkeit gewichtet; wer sie an eine Kürzeste-Wege-Routine übergibt, berechnet also den Weg über die am wenigsten ähnlichen Verbindungen. Wenn Sie aus einer Ähnlichkeit eine Distanz brauchen, wandeln Sie bewusst um: d = 1 - s für eine Ähnlichkeit in [0, 1], oder d = 1/s, oder d = -log s. Jede Wahl ändert die Rangfolge der Wege, also ist sie eine Modellierungsentscheidung und keine Formalität.

5. Welchen Algorithmus die Gewichte für Sie wählen

Sobald die Verknüpfungsregel additiv ist, entscheidet allein die Form der Gewichtsfunktion über den Algorithmus. Das ist der praktische Kern der Unterscheidung zwischen gewichtet und ungewichtet.

Zwei Einträge dieser Tabelle verdienen eine Anmerkung. 0-1-BFS beruht auf der schönen Beobachtung, dass man bei Gewichten von nur 0 oder 1 überhaupt keinen Heap braucht: Eine doppelseitige Warteschlange hält die Front kostenlos sortiert, und so erhält man lineare Zeit zurück. Der Johnson-Algorithmus aus seiner Arbeit von 1977 im Journal of the ACM ist der Standardweg, Dijkstras Geschwindigkeit auf Graphen mit negativen Kanten zu erhalten: Er fügt eine Potenzialfunktion hinzu, die jede umgewichtete Kante nichtnegativ macht und dabei erhält, welche Wege am kürzesten sind.

Es gibt auch ein bemerkenswertes Resultat an der Grenze zum ungewichteten Fall. Thorup zeigte 1999, dass kürzeste Wege von einer Quelle in einem ungerichteten Graphen mit positiven ganzzahligen Gewichten in linearer Zeit berechnet werden können, genauso schnell wie BFS, indem man die Struktur ganzzahliger Gewichte ausnutzt, statt Distanzen zu vergleichen. Für beliebige reelle Gewichte im Vergleichs-Additions-Modell ist kein vergleichbares Linearzeit-Resultat bekannt, was daran erinnert, dass „gewichtet“ kein einzelnes Problem ist, sondern eine Familie, deren Schwierigkeit davon abhängt, wie die Gewichte aussehen.

6. Negative Gewichte und warum Dijkstra scheitert

Dijkstras Notiz von 1959 setzte nichtnegative Gewichte voraus, und diese Annahme ist tragend, nicht dekorativ. Der Algorithmus ist gierig: Sobald er einen Knoten aus der Warteschlange nimmt, erklärt er ihn für abgeschlossen und betrachtet ihn nie wieder. Das ist nur korrekt, wenn kein später gefundener Weg billiger sein kann, und genau das garantiert Nichtnegativität, da das Verlängern eines Weges seine Kosten nur erhöhen kann.

Führen Sie eine einzige negative Kante ein, und die Garantie fällt. Hier ist ein Gegenbeispiel, klein genug, um es von Hand nachzuvollziehen, und frei von Gleichständen, sodass die Entnahmereihenfolge eindeutig ist:

Verfolgen Sie es: Die Warteschlange entnimmt S bei 0 und relaxiert A auf 1 und C auf 3. Sie entnimmt A bei 1 und relaxiert B auf 2. Sie entnimmt B bei 2 und markiert es als abgeschlossen. Erst dann entnimmt sie C bei 3 und findet den Bogen C → B mit Gewicht -5, der B eine Distanz von -2 geben würde. Da B bereits abgeschlossen ist, wird die Verbesserung verworfen, und der Algorithmus meldet 2 statt -2.

Zwei Klarstellungen, die wichtiger sind als das Gegenbeispiel selbst:

• Negative Gewichte sind nicht dasselbe wie negative Kreise. Ein Graph kann negative Kanten und trotzdem wohldefinierte kürzeste Wege haben, und genau diesen Fall behandelt Bellman-Ford in O(nm). Was das Problem vollständig zerstört, ist ein Kreis mit negativem Gesamtgewicht, weil man ihn wiederholt durchlaufen und die Kosten gegen minus unendlich treiben kann. Bellman-Ford erkennt diese Situation, statt stillschweigend Unsinn zu liefern.
• In einem ungerichteten Graphen ist schon eine einzige negative Kante ein negativer Kreis. Laufen Sie sie hin und zurück, und Sie haben 2w < 0 bezahlt. Negative Gewichte sind also faktisch ein Thema gerichteter Graphen; in ungerichteten Graphen wird das Problem kürzester Kantenzüge unbeschränkt und das Problem kürzester einfacher Wege NP-schwer. Der begleitende Leitfaden zu gerichteten und ungerichteten Graphen behandelt diese Grenze.

Negative Gewichte sind nichts Exotisches. Arbitrageketten bewerten Währungsumrechnungen als Produkte, die zu Summen negativer Logarithmen werden, und ein profitabler Kreis erscheint im Modell als negativer Kreis. Das ist die Standardanwendung der Erkennung negativer Gewichte im Lehrbuch, und deshalb ist Bellman-Ford seinen zusätzlichen Faktor n wert.

7. Probleme, die es nur mit Gewichten gibt

Manche Fragen sind ohne Gewichte nicht schwerer, sondern leer. Der deutlichste Fall ist der minimale Spannbaum.

In einem ungewichteten zusammenhängenden Graphen hat jeder Spannbaum genau n - 1 Kanten, also ist jeder Spannbaum minimal, und jeder Durchlauf löst das Problem: Der BFS- oder DFS-Baum ist bereits eine Antwort. Fügen Sie Gewichte hinzu, und die Frage wird echt, weil Spannbäume nun verschiedene Gesamtkosten haben; den billigsten zu finden, gelang Borůvka 1926, Kruskal 1956 und Prim 1957 jeweils auf eigene Weise.

Im durchgehenden Beispiel nimmt der minimale Spannbaum die Kanten {A,B}, {B,C}, {C,D} und {D,E} mit Gesamtgewicht 5 und verwirft die teure Kante {A,D} mit 7. Ungewichtet wären alle vier Spannbäume dieses Graphen gleich gut.

Der maximale Fluss ist das Spiegelbild des Spannbaum-Falls. Kapazitäten sind die Gewichtsfunktion, ein ungewichtetes Flussnetzwerk bedeutet also Einheitskapazitäten, und in diesem Spezialfall reduziert sich der maximale Fluss nach dem Satz von Menger auf das Zählen kantendisjunkter Wege. Ahuja, Magnanti und Orlins Network Flows ist das Standardwerk für die allgemeine gewichtete Behandlung, bei der jeder Bogen typischerweise eine Kapazität und Kosten trägt, also zwei Gewichtsfunktionen auf einem Graphen.

8. Gewichte speichern und die Falle „Null oder Unendlich“

Beide Standarddarstellungen lassen sich auf naheliegende Weise erweitern, und beide haben eine Fehlerquelle, die man benennen sollte.

Adjazenzmatrix. Statt 0 und 1 enthält der Eintrag (u, v) das Gewicht dieser Kante. Die Falle liegt auf der Hand: Was steht in den Zellen ohne Kante? Null ist der verlockende Standardwert und falsch, denn null ist ein völlig zulässiges Gewicht, und die beiden Fälle werden ununterscheidbar. Verwenden Sie ∞ für „keine Kante“ bei kürzesten Wegen, da das das neutrale Element der Minimierung ist, und lassen Sie 0 auf der Diagonalen. In einer ungewichteten Matrix bedeutet dieselbe Zelle mit dem Wert 0 „keine Kante“, und genau deshalb bricht Code, der von ungewichtet auf gewichtet portiert wird, an dieser Stelle.

ungewichtet       A[u][v] = 1 wenn verbunden, sonst 0
gewichtet         A[u][v] = w(u,v) wenn verbunden, sonst ∞      (0 auf der Diagonalen)

Sentinel-Bug      A[u][v] = 0 für „keine Kante“ macht eine Kante mit Gewicht 0
                  unsichtbar, und jede Distanz fällt auf 0 zusammen

Adjazenzliste. Jeder Eintrag wird zu einem Paar statt eines bloßen Knotens, die Liste enthält also (Nachbar, Gewicht). Sonst ändert sich nichts, und deshalb ist die Adjazenzliste der Standard für gewichtete Probleme: Der Speicheraufwand ist eine Zahl pro gespeicherter Kante, und die Durchlaufschleife ist identisch.

Ein drittes Format ist speziell für gewichtete Graphen wichtig. Die Kantenliste aus Tripeln (u, v, w) ist die natürliche Eingabe für den Kruskal-Algorithmus, der die ganze Liste nach Gewicht sortiert, und für Bellman-Ford, der jede Kante der Reihe nach relaxiert. Keiner von beiden braucht Nachbarschaftsabfragen, also braucht keiner überhaupt eine Adjazenzstruktur.

9. Aus dem Grad wird die Stärke

Gewichte ändern nicht nur Algorithmen, sondern auch beschreibende Kennzahlen. Das gewichtete Gegenstück zum Grad eines Knotens ist seine Stärke, die Summe der Gewichte seiner inzidenten Kanten:

deg(v)  =  Anzahl inzidenter Kanten          die ungewichtete Zählung
s(v)    =  ∑ w(e)  über Kanten an v           die gewichtete Summe

Barrat, Barthélemy, Pastor-Satorras und Vespignani führten den Begriff 2004 in ihrer PNAS-Arbeit über gewichtete Netzwerke ein, und er ist wichtig, weil beide Größen Knoten völlig unterschiedlich einstufen können. Ein Flughafen mit vielen winzigen Regionalstrecken hat hohen Grad und geringe Stärke; ein Drehkreuz mit vier riesigen Langstrecken hat geringen Grad und hohe Stärke. Die Frage „Welcher Flughafen ist der wichtigste?“ hat je nach berechneter Größe eine andere Antwort, und keine davon ist falsch.

Dieselbe Spaltung zieht sich durch die übrige Netzwerkanalyse. Newmans Arbeit „Analysis of weighted networks“ von 2004 zeigt, wie Clusterkoeffizienten, Modularität und Zentralität jeweils gewichtete Versionen erhalten und dass gewichtete und ungewichtete Versionen einer Kennzahl auf denselben Daten häufig nicht übereinstimmen. Wenn Sie eine Netzwerkkennzahl angeben, ist die Angabe, ob sie die Gewichte verwendet, keine Fußnote, sondern Teil der Definition.

10. Wann man Gewichte hinzufügt und wann nicht

Gewichte sind nicht umsonst. Sie kosten Linearzeit-Algorithmen, sie fügen bei jedem Schritt eine Modellierungsentscheidung hinzu, und sie bringen eine Skalenabhängigkeit mit, die ein ungewichteter Graph schlicht nicht hat. Greifen Sie zu ihnen, wenn die Antwort wirklich von Größenordnungen abhängt:

• Fügen Sie Gewichte hinzu, wenn die Kanten messbar ungleich sind, und zwar so, dass es die Entscheidung ändert: Straßenlängen, Verbindungskapazitäten, Transaktionsbeträge, Korrelationsstärken, Ähnlichkeitswerte.
• Bleiben Sie ungewichtet, wenn die Relation ihrem Wesen nach binär ist (Nachbarschaft von Ländern, Vorhandensein einer Abhängigkeit), wenn Ihre Zahlen verrauschte Stellvertreter sind, die Sie nicht verteidigen würden, oder wenn die Frage rein strukturell ist, etwa Zusammenhang oder Bipartitheit.
• Setzen Sie stattdessen einen Schwellenwert, wenn Gewichte existieren, aber unzuverlässig sind. Wer Kanten oberhalb eines Grenzwerts behält und den Rest verwirft, macht aus einem verrauschten gewichteten Graphen einen vertretbaren ungewichteten. Nennen Sie den Grenzwert, denn die Ergebnisse hängen meist davon ab.

Zwei Warnungen speziell für gewichtete Daten. Erstens zählt die Skala: Multipliziert man jedes Gewicht mit einer positiven Konstanten, bleiben kürzeste Wege und minimale Spannbäume unverändert, da beide eine Summe minimieren, aber jede Kennzahl, die Gewichte mit einem absoluten Schwellenwert vergleicht, ändert sich, und ein negativer Faktor kehrt das Problem vollständig um. Zweitens müssen die Einheiten übereinstimmen , bevor Gewichte addiert werden. Minuten und Kilometer in einer Gewichtsfunktion zu mischen ergibt Zahlen, die kein Algorithmus interpretieren kann, und nichts im Code wird sich beschweren.

11. Häufige Fehler

• BFS auf einem gewichteten Graphen ausführen. Der häufigste von allen. Sie liefert den Weg mit den wenigsten Kanten, also eine korrekte Antwort auf eine andere Frage, und der Fehler ist unbeschränkt, wie Abschnitt 3 zeigt.
• 0 als Markierung für „keine Kante“ verwenden. Das geht gut, bis es eine echte Kante mit Gewicht 0 gibt, dann ist es stillschweigend falsch. Verwenden Sie bei Minimierungsproblemen Unendlich.
• Einen Ähnlichkeitsgraphen an eine Kürzeste-Wege-Routine übergeben. Sie findet getreulich die Route über die schwächsten Verbindungen. Wandeln Sie Ähnlichkeit zuerst in Distanz um und geben Sie an, wie.
• Bei negativen Gewichten zu Dijkstra greifen. Er verliert nicht nur auf manchen Eingaben seine Optimalitätsgarantie, er liefert konkret falsche Zahlen, wie in Abschnitt 6. Verwenden Sie Bellman-Ford oder für alle Paare Johnson.
• Annehmen, eine negative Kante mache das Problem kaputt. Nur ein negativer Kreis macht kürzeste Wege undefiniert. Bellman-Ford behandelt den Rest und meldet den Kreis, falls es einen gibt.
• Gewichte mit verschiedenen Einheiten addieren. Minuten plus Kilometer ergibt keinen Sinn, und kein Algorithmus wird es Ihnen sagen.
• Eine gewichtete Netzwerkkennzahl angeben, ohne es zu sagen. Grad und Stärke sowie die daraus abgeleiteten Zentralitäten ordnen dieselben Knoten regelmäßig unterschiedlich.
• Vergessen, dass die Struktur unverändert bleibt. Zusammenhang, Bipartitheit und Gradfolgen hängen nicht von w ab. Wenn ein gewichteter Algorithmus eine Antwort liefert, die einer davon widerspricht, liegt der Fehler in der Gewichtung, nicht in der Theorie.

12. Glossar

14. Quellen

Die Definitionen, Algorithmen und Zuschreibungen oben stammen aus diesen Quellen, in chronologischer Reihenfolge.

1. Borůvka, O. (1926). "O jistém problému minimálním" (Über ein gewisses Minimalproblem). Práce Moravské Přírodovědecké Společnosti 3, 37 bis 58. Der früheste Algorithmus für minimale Spannbäume.
2. 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.
3. Prim, R. C. (1957). "Shortest Connection Networks and Some Generalizations." Bell System Technical Journal 36(6), 1389 bis 1401.
4. Bellman, R. (1958). "On a Routing Problem." Quarterly of Applied Mathematics 16(1), 87 bis 90. Kürzeste Wege, die negative Gewichte vertragen.
5. Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1, 269 bis 271. Hier wird die Nichtnegativitätsannahme formuliert.
6. Moore, E. F. (1959). "The Shortest Path Through a Maze." Proceedings of an International Symposium on the Theory of Switching, Teil II, 285 bis 292. Harvard University Press. Der Fall mit Einheitsgewichten, heute als BFS bekannt.
7. Johnson, D. B. (1977). "Efficient Algorithms for Shortest Paths in Sparse Networks." Journal of the ACM 24(1), 1 bis 13. Umgewichtung zur Beseitigung negativer Kanten.
8. 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. Dijkstra in O(m + n log n).
9. Ahuja, R. K., Magnanti, T. L. und Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs: Prentice Hall. Das Standardwerk zu Kapazitäten und Kosten als Gewichten.
10. Thorup, M. (1999). "Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time." Journal of the ACM 46(3), 362 bis 394.
11. West, D. B. (2001). Introduction to Graph Theory, 2. Auflage. Upper Saddle River: Prentice Hall.
12. Barrat, A., Barthélemy, M., Pastor-Satorras, R. und Vespignani, A. (2004). "The Architecture of Complex Weighted Networks." Proceedings of the National Academy of Sciences 101(11), 3747 bis 3752. Quelle der Knotenstärke.
13. Newman, M. E. J. (2004). "Analysis of Weighted Networks." Physical Review E 70, 056131. Gewichtete Versionen der Standardkennzahlen für Netzwerke.
14. Bondy, J. A. und Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer. Quelle der Definition gewichteter Graphen in Abschnitt 1.
15. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage. Cambridge, Massachusetts: MIT Press.
16. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer.