R3 Flussprobleme
Maximaler Fluss, Minimaler Schnitt ( Min-Cut / Max-Flow)
Griffig formuliert lautet die Regel Min-Cut, Max-Flow. Das bedeutet nichts anderes, als dass ein Schnitt an der Stelle des Netzwerks mit der geringsten Kapazität (Min-Cut) den maximalen Fluss (Max-Flow) bestimmt.
Schnitt
Einen Schnitt durch das Netzwerk kann man sich recht bildlich vorstellen, in dem man alle Kanten zerschneidet, sodass der Graph in zwei Teile zerfällt. Im vorliegenden Fall sind Schnitte zwischen Quelle und Senke von Interesse.
Etwas formaler ausgedrückt:
Die Knoten V werden in zwei Mengen U und U‘ geteilt:
V={U;U'}
Die Menge U enthalte die Quelle und U‘ die Senke.
Die Kanten T die U und 
verbinden sind die Schnittkanten. Die Schnittkanten lassen sich wiederum in Vorwärtskanten TV , die von U nach führen und die Rückwärtskanten TR, die von nach U führen, unterteilen.
Minimaler Schnitt
Soweit zu Schnitten allgemein, wir sind auf der Suche nach dem minimalen Schnitt. Nun könnte man auf die Idee kommen, alle möglichen Schnitte zu bilden und zu schauen, wie groß die Kapazität der Schnitte ist. Es gibt im Allgemeinen sehr viele Möglichkeiten für Quelle-Senke-Schnitte. Von daher ist das Vorgehen alle möglichen Quelle-Senke-Schnitte durchzuprobieren nicht zielführend.
Flussvergrößernde Kette
Eine Flussvergrößernde Kette wird auch als Flussvergrößender Pfad bezeichnet, im Englischen „augmenting path“.
Der Ansatz zum Auffinden des maximalen Flusses und auch des minimalen Schnittes läuft über die Flussvergrößernde Kette. Dabei wird eine Kette (=ein Weg der auch Pfeile entgegen der Richtung benutzt) gesucht, die von der Quelle zu Senke führt und es ermöglicht den Fluss zu vergrößern.
Dabei sind zwei Fälle zu unterscheiden:
Fall 1: Fluss xij geringer als Kapazität kij
Als Teil dieser Kette kommen Kanten infrage, auf denen der aktuelle Fluss xij geringer als die Kapazität kij ist, also auf denen der Fluss noch gesteigert werden kann. Wenn von der Quelle zur Senke ein Weg p der aus solchen Kanten besteht, gefunden werden kann, lässt sich der Fluss durch das gesamte Netzwerk vergrößern. Die Kante auf dem Weg p, die die geringste Vergrößerung zulässt, ist maßgeblich für die Vergrößerung des Flusses.
In der nachfolgenden Abbildung ist basierend auf einem vorab vorhanden Fluss eine Flussvergrößernde Kette eingetragen.
Eigentlich ist dieser Fall recht trivial. Es gibt allerdings noch ein zweiten Fall, der auch betrachtet werden muss, um sicher zu gehen, dass der maximale Fluss gefunden wird.
Fall 2: Fluss xij größer als 0
Auf der Suche nach der Flussvergrößernden Kette p müssen auch alle Kanten mit einem Fluss größer als 0 betrachtet werden. Hintergrund ist, dass auch durch Senken des Flusses auf einer Kante der Fluss zwischen Quelle und Senke insgesamt vergrößert werden kann, wie nachfolgende Skizze zeigt.
Durch Senken des Flusses von B nach C um 1 kann der Fluss von Quelle zu Senke erhöht werden. Bildlich gesprochen wird die eine Einheit die über die Kante (B;C) fließt über (B;D) umgeleitet. Dadurch kann die freie Kapazität auf (A;C) genutzt werden.
Eine Flussvergrößernde Kette kann Kanten aus beiden Fällen enthalten. Die mögliche Flusserhöhung ergibt sich aus der minimalen Änderungsmöglichkeit der Kanten beider Fälle.
Die Flusserhaltung, d.h. dass die Summe der Zu- und Abflüsse in allen Zwischenknoten erhalten bleibt, ist gewährleistet:
- Fall 1 / Fall 1: Der Zufluss zu einem Knoten wird gesteigert und der Abfluss in gleichem Maß.
- Fall 2 / Fall 2: Der Zufluss in einen Knoten wird gesenkt und der Abfluss ebenfalls.
- Fall 1 / Fall 2: Der Zufluss in einen Knoten über eine Kante wird erhöht, dafür wird aber im gleichen Maß der Zufluss über eine andere Kante gesenkt.
- Fall 2 / Fall 1: Der Abfluss über eine ausgehende Kante wird gesenkt, dafür wird der Abfluss über eine andere Kante erhöht.
Zusammenhang zwischen Maximalem Fluss und Flussvergrößernder Kette
- Solange eine Flussvergrößernde Kette existiert, ist noch nicht der Maximale Fluss erreicht.
- Gibt es keinen Flussvergrößernde Kette mehr, ist der Maximale Fluss erreicht.
