Math
Graphentheorie
Kürzeste Wege, Spannbäume und Flüsse auf einem Graphen, gezeichnet während sie berechnet werden: Dijkstras Welle, Kruskals Inseln, die Pfade von Edmonds-Karp und der Schnitt, der dem Fluss gleicht.
Was passiert
Vierzig leuchtende Knoten, zufällig verstreut, jeder mit seinen vier nächsten verbunden und mit dem, was nötig ist, damit der Graph ein Stück bleibt - hundert Kanten, ihre Längen die Gewichte und je eine Kapazität von eins bis neun. Drei Fragen, jede vor deinen Augen Schritt für Schritt beantwortet. Kürzeste Wege: Dijkstra schließt Knoten in der Reihenfolge ihres Abstands von der Quelle S ab, und die abgeschlossene Menge breitet sich von S wie eine Welle aus - ein Knoten ist fertig, sobald sein Abstand nicht mehr besser werden kann - bis die Senke T erreicht ist und ihr Weg mit den Abständen entlang aufleuchtet. Bellman-Ford, ein Verfahren ganz ohne Prioritätswarteschlange, stimmt Knoten für Knoten zu, und die Dreiecksungleichung gilt auf jeder Kante. Spannbaum: Kruskal nimmt die Kanten von leicht nach schwer, behält eine, die zwei Inseln verbindet (grün), verwirft eine, die eine Schleife schließen würde (rot), und der Baum ist bei N − 1 Kanten fertig; jede verworfene Kante ist die schwerste auf der Schleife, die sie geschlossen hätte - darum ist die gierige Wahl die billigste Verdrahtung. Fluss: Edmonds-Karp findet den kürzesten Weg mit Restkapazität von S nach T, schiebt den Engpass hindurch und wiederholt das, die Kanten füllen sich bis zu ihren Kapazitäten, bis kein Weg mehr da ist - und dann leuchtet der Schnitt zwischen dem, was S noch erreicht, und dem Rest, und seine Kapazität gleicht dem Fluss: max-flow = min-cut. Klick auf einen Knoten macht ihn zur Quelle, Rechtsklick zur Senke, zieh einen Knoten und jede Antwort wird für die neuen Längen neu berechnet.
Gleichungen des Moduls
Gleichungen Graph: N Punkte in [−1, 1]² aus dem gemeinsamen Würfel (Seed 3, N = 40); jeder verbunden mit seinen k = 4 nächsten Nachbarn, dazu der euklidische minimale Spannbaum, damit der Graph zusammenhängend ist; 100 Kanten, Gewicht = Länge, Kapazität 1 … 9 vom selben Würfel; S = Knoten ganz links (29), T = Knoten ganz rechts (39) Dijkstra: d(S) = 0, die anderen ∞; den unerledigten Knoten mit kleinstem d festsetzen, d(v) = min(d(v), d(u) + w(u, v)) für seine Nachbarn relaxieren; festgesetzte Knoten verbessern sich nie; d(T) = 2.0906 über 6 Kanten; Bellman–Ford (N − 1 Runden über alle Kanten) stimmt bis auf 10^−12 überein; d(v) ≤ d(u) + w(u, v) auf jeder Kante Kruskal: Kanten nach Gewicht, e behalten, wenn seine Enden in verschiedenen Komponenten liegen (Union-Find); N − 1 = 39 behalten, 61 übersprungen, Gewicht 8.4480; die erste übersprungene Kante ist die 12. betrachtete; Kreiseigenschaft: eine übersprungene Kante ist mindestens so schwer wie jede Kante auf dem Baumpfad zwischen ihren Enden - also ist der gierige Baum minimal Edmonds–Karp: Restkapazität c(u, v) − f(u, v); Breitensuche von S nach T über Kanten mit Restkapazität, den Engpass b entlang des Weges schieben, f(u, v) += b, f(v, u) −= b; wiederholen, bis kein Weg mehr existiert; 13 Wege mit Engpässen 2 1 2 1 1 1 1 1 2 1 1 1 1, Fluss 16; der Schnitt (Knoten, die S noch erreicht | der Rest) hat Kapazität 16, 35 Knoten auf der Quellenseite; Erhaltung: Nettofluss 0 an jedem Knoten außer S und T einfacher Graph: keine Schleifen, keine parallelen Kanten; Σ deg(v) = 2E; Eulerkreis genau dann, wenn zusammenhängend und jeder Grad gerade, Eulerweg genau dann, wenn genau zwei Grade ungerade sind; bei c Komponenten behält Kruskal N − c Kanten
