Max-Flow-Min-Cut ist ein fundamentales Problem der Graphentheorie: Wie viel „Fluss“ (Daten, Wasser, Güter, Verkehr) passt maximal von einer Quelle s zu einer Senke t durch ein Netzwerk mit begrenzten Kantenkapazitäten? Die überraschende Antwort liefert das Max-Flow-Min-Cut-Theorem: Der maximale Fluss entspricht exakt der Kapazität des kleinsten „Schnitts“, der Quelle und Senke trennt. Anders als viele Probleme der diskreten Optimierung ist Max-Flow in Polynomzeit lösbar.
Das Flussproblem
Gegeben ist ein gerichteter Graph, dessen Kanten Kapazitäten tragen (eine Spezialform von Kantengewichten). Ein gültiger Fluss erfüllt zwei Bedingungen: Die Menge pro Kante liegt zwischen 0 und ihrer Kapazität, und in jedem Knoten außer Quelle und Senke ist der Zufluss gleich dem Abfluss (Flusserhalt). Der Wert des Flusses ist die Gesamtmenge, die an der Quelle austritt (bzw. an der Senke ankommt).
Algorithmen
- Ford-Fulkerson: Solange es im Residualgraphen einen augmentierenden Pfad von s nach t gibt, wird entlang dieses Pfades mehr Fluss geschickt. Die Suche läuft mit Tiefensuche (DFS), die Laufzeit ist O(E · f) mit Flusswert f — bei großen Zahlenwerten und irrationalen Kapazitäten kann das langsam werden.
- Edmonds-Karp: Dieselbe Idee, aber der Pfad wird per Breitensuche (BFS) als kürzester augmentierender Pfad gewählt — das garantiert O(V · E²) und macht den Algorithmus damit unbedingt polynomiell.
- Dinic: Erreicht mit Blocking-Flows O(V² · E) und ist in der Praxis oft am schnellsten.
Das Min-Cut-Theorem
Ein Schnitt (Cut) teilt die Knoten in zwei Gruppen S (mit Quelle) und T (mit Senke); seine Kapazität ist die Summe aller Kantenkapazitäten von S nach T. Das 1956 von Ford und Fulkerson bewiesene Theorem besagt: Maximaler Fluss = minimale Schnittkapazität. Jeder Fluss ist automatisch durch jeden Schnitt begrenzt (schwache Dualität), und es existiert immer ein Schnitt, der den Fluss exakt erreicht (starke Dualität). Damit findet man mit einem Max-Flow-Algorithmus gleichzeitig den teuersten Engpass des Netzes.
Anwendungen
- Netzplanung: Maximale Daten- oder Transportmengen berechnen und Engpässe (Min-Cuts) identifizieren.
- Bipartites Matching: Wer passt zu wem? Eine Super-Quelle und -Senke plus Kapazität 1 pro Kante verwandeln das Zuordnungsproblem in ein Flussproblem (verwandt mit Matching und perfektem Matching in bipartiten Graphen).
- Bildsegmentierung: Graph-Cuts trennen Vorder- und Hintergrund in Bildern.
- Zuordnung und Evakuierung: Personen, Aufgaben oder Güter optimal verteilen.
Verwandt, aber ein anderes Netzwerk-Verfahren: Dijkstra sucht kürzeste Wege statt maximaler Flüsse. Im Gegensatz zu NP-vollständigen Problemen wie Graphfärbung oder Subset-Sum bleibt Max-Flow effizient lösbar.