Maximaler Fluss Rechner

Pseudocode

Alle Maximalfluss-Algorithmen dieser Familie sind dieselbe Schleife: finde einen Weg von der Quelle zur Senke mit freier Kapazität, schiebe so viel wie möglich, wiederhole. Sie unterscheiden sich nur darin, wie sie diesen Weg wählen.

MaxFluss(graph, s, t):
    fluss = 0
    Residualgraph bauen: cap(u,v) vorwärts, 0 rückwärts

    solange es im Residualgraph einen augmentierenden
          Pfad P von s nach t gibt:
        engpass = kleinste Restkapazität entlang P
        für jede Kante (u, v) in P:
            residual[u][v] -= engpass
            residual[v][u] += engpass   // Rücknahmekante
        fluss += engpass

    gib fluss zurück

// Ford-Fulkerson: findet P per DFS (beliebiger Pfad)
// Edmonds-Karp:   findet P per BFS (kürzester Pfad)

Die rückwärts gerichtete Residualkante ist der Teil, der falsch aussieht und tatsächlich unverzichtbar ist. Sie erlaubt es einem späteren augmentierenden Pfad, zuvor geschobenen Fluss zurückzunehmen, sodass der Algorithmus eine schlechte frühe Wahl ohne Backtracking wieder verlässt. Ohne diese Rücknahmekanten bleibt die gierige Schleife bei einem suboptimalen Fluss stecken.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe Edmonds-Karp auf dem Standardbeispiel aus, bei dem eine gierige erste Wahl später zurückgenommen werden muss.

Beispielgraph: Gerichtete Kapazitäten: S nach A (10), S nach B (10), A nach B (2), A nach T (4), B nach T (9).

1. Augmentierung 1. BFS findet S nach A nach T. Der Engpass ist min(10, 4) = 4. Schiebe 4. Gesamtfluss 4. Das Residual S-A sinkt auf 6 und A-T auf 0.
2. Augmentierung 2. BFS findet S nach B nach T. Der Engpass ist min(10, 9) = 9. Schiebe 9. Gesamtfluss 13. Das Residual S-B sinkt auf 1 und B-T auf 0.
3. Augmentierung 3. A-T und B-T sind beide gesättigt, es bleibt keine direkte Route. BFS findet keinen augmentierenden Pfad mehr: T zu erreichen erforderte A-T oder B-T, und beide sind voll.
4. Den Schnitt prüfen. Welche Kanten sind gesättigt? A-T mit 4 und B-T mit 9, Gesamtkapazität 13. Entfernt man sie, ist T von S getrennt, es ist also ein Schnitt der Kapazität 13, und der Fluss von 13 erreicht ihn genau.
5. Warum die Rücknahmekante zählt. Wäre der erste augmentierende Pfad S nach A nach B nach T mit 2 gewesen, so wäre die Kante A-B auf eine Weise gesättigt, die hier nichts blockiert. In Graphen jedoch, in denen der gierige Pfad Kapazität wegnimmt, die ein späterer Pfad braucht, erlaubt die rückwärtige Residualkante B nach A, diese 2 Einheiten zurückzuschieben und umzuleiten. Der Algorithmus muss nie ausdrücklich zurücksetzen.

Der maximale Fluss beträgt 13, und der minimale Schnitt ist das Kantenpaar A-T und B-T mit Gesamtkapazität 13. Dass beide Zahlen gleich sind, ist kein Zufall: das ist der Max-Flow-Min-Cut-Satz.

Komplexität und woher sie kommt

Zeit: O(V·E^2) mit Edmonds-Karp · Speicher: O(V + E)

Ford-Fulkerson mit beliebiger Pfadwahl läuft in O(E mal Maximalfluss), denn jede Augmentierung fügt mindestens eine Einheit hinzu, während die Pfadsuche O(E) kostet. Das ist pseudopolynomiell und wirklich schlecht: bei Kapazitäten in Milliardenhöhe kann es Milliarden Augmentierungen brauchen, und bei irrationalen Kapazitäten terminiert es womöglich gar nicht. Edmonds-Karp behebt das, indem stets der kürzeste augmentierende Pfad per BFS gewählt wird. Die Distanz von der Quelle zur Senke sinkt nie, und jede Kante kann höchstens V/2 mal Engpass sein, was die Zahl der Augmentierungen auf O(VE) und den Gesamtaufwand auf O(V mal E hoch 2) begrenzt. Dinic bündelt Augmentierungen in Phasen über einen Niveaugraphen und verbessert das auf O(V hoch 2 mal E), bei Einheitskapazitäten auf O(E mal Wurzel aus V).

Wann Maximaler Fluss passt und wann nicht

Die Wahl hängt vor allem von der Größenordnung der Kapazitäten und der Graphgröße ab.

Häufige Fehler

• Die rückwärtigen Residualkanten weglassen. Ohne sie kann der Algorithmus eine frühere schlechte Augmentierung nicht zurücknehmen und endet bei einem Fluss, der lediglich maximal im Sinne von unerweiterbar ist, nicht maximal im Wert. Das ist der häufigste Maximalfluss-Fehler und liefert plausible, aber zu kleine Antworten.
• DFS-Pfadwahl bei großen Kapazitäten. Reines Ford-Fulkerson mit DFS kann bei ungünstigen Graphen eine Augmentierung je Flusseinheit benötigen. Das klassische Beispiel mit Kapazitäten von einer Million und einer Engpasskante von eins braucht eine Million Durchläufe. BFS macht die Anzahl unabhängig von den Kapazitätswerten.
• Vergessen, dass Flusserhaltung Quelle und Senke ausnimmt. Jeder andere Knoten muss gleich viel Zufluss wie Abfluss haben. Eine Prüfung der Erhaltung an Quelle oder Senke schlägt immer fehl und stiftet beim Schreiben von Tests regelmäßig Verwirrung.
• Annehmen, der maximale Fluss sei eindeutig. Der Wert des maximalen Flusses ist eindeutig; die ihn erreichende Flusszuweisung meist nicht, und der minimale Schnitt ebenso wenig, wenn mehrere dieselbe Kapazität haben. Tests müssen den Wert prüfen, nicht eine bestimmte Zuweisung Kante für Kante.
• Knotenkapazitäten als Kantenkapazitäten modellieren. Hat ein Knoten selbst eine Durchsatzgrenze, muss er in einen Eingangs- und einen Ausgangsknoten aufgeteilt werden, verbunden durch eine Kante dieser Kapazität. Die Grenze auf die anliegenden Kanten anzuwenden ergibt ein anderes, falsches Problem.

Häufig gestellte Fragen

Was ist das Maximalflussproblem?

Gegeben ein gerichteter Graph, in dem jede Kante eine Kapazität hat, sowie eine Quelle und eine Senke, fragt der Maximalfluss nach der größten Rate, mit der Material von der Quelle zur Senke fließen kann, ohne eine Kantenkapazität zu überschreiten und unter Erhaltung des Flusses an jedem Zwischenknoten. Er modelliert Durchsatz in Leitungen, Netzen, Logistik und Ablaufplanung.

Was besagt der Max-Flow-Min-Cut-Satz?

Der Wert des maximalen Flusses von der Quelle zur Senke ist stets gleich der Kapazität des minimalen Schnitts, der beide trennt. Anschaulich kann der Fluss keinen Schnitt übersteigen, da alles ihn queren muss, und wenn kein augmentierender Pfad mehr bleibt, definieren die im Residualgraph erreichbaren Knoten einen Schnitt, dessen Kapazität der Fluss genau erreicht.

Was ist der Unterschied zwischen Ford-Fulkerson und Edmonds-Karp?

Es ist dieselbe Methode augmentierender Pfade mit unterschiedlicher Pfadwahl. Ford-Fulkerson lässt die Wahl offen, üblicherweise DFS, wodurch die Laufzeit von den Kapazitätswerten abhängt und katastrophal langsam werden kann. Edmonds-Karp nimmt stets den kürzesten augmentierenden Pfad per BFS, was den Aufwand unabhängig von den Kapazitäten auf O(V mal E hoch 2) begrenzt.

Warum brauchen Maximalfluss-Algorithmen Residualkanten?

Weil der Algorithmus gierig ist und nicht vorausschauen kann. Eine rückwärtige Residualkante steht für die Möglichkeit, bereits über diese Kante geschobenen Fluss zurückzunehmen, sodass ein späterer augmentierender Pfad frühere Entscheidungen umleiten kann. Genau das erlaubt einer rein vorwärts laufenden Schleife, ohne Backtracking ein echtes Optimum zu erreichen.

Wie ist die Zeitkomplexität des Maximalflusses?

Edmonds-Karp läuft in O(V mal E hoch 2). Dinic verbessert das auf O(V hoch 2 mal E) und bei Einheitskapazitäten auf O(E mal Wurzel aus V), weshalb er für bipartites Matching bevorzugt wird. Reines Ford-Fulkerson ist O(E mal Maximalflusswert), also pseudopolynomiell statt polynomiell.