Gegeben sei ein gerichteter Graph , gewichtet mit einer
Funktion
. Die Gewichte
werden hier als Kantenkapazitäten interpretiert und beschreiben
die maximale Zahl von Transporteinheiten, die pro Zeiteinheit durch diese Kante fließen können.
Zwei Knoten aus
sind als Quelle
und die Senke
ausgezeichnet. Modelliert werden mit
einem solchen Graph die Transportkapazitäten zwischen diversen Orten und
gesucht wird der maximale Fluss, der von der Quelle ausgeht, durch die
inneren Knoten fließt und an der Senke ankommt. Dabei muss die Flussmenge,
die in einen inneren Knoten hineinfließt, übereinstimmen mit der Flussmenge,
die aus ihm herausfließt.
Formal:
Sei die Menge aller Vorgängerknoten von Knoten
.
Sei
die Menge aller Nachfolgerknoten von Knoten
.
Ein Fluss ist eine Funktion
mit:
Gesucht ist nun der maximale Gesamtfluss
.
Im folgenden Graph ist jede Kante beschriftet mit ihrem aktuellen Fluss und ihrer maximalen Kapazität. Es fließen insgesamt 10 Einheiten von der Quelle s zur Senke t.
Um den maximalen Fluss zu berechnen, sucht man zunächst sogenannte erweiternde
Wege. Ein erweiternder Weg in ist eine
Folge von Knoten, beginnend bei
und endend bei
, wobei für zwei aufeinanderfolgende Knoten
und
gilt:
Längs eines erweiternden Weges kann der Fluss vergrößert werden, indem man durch die Vorwärtskanten zusätzliche Einheiten fließen lässt und in den Rückwärtskanten den Fluss verringert.
Der Algorithmus von Ford-Fulkerson versucht solange den aktuellen Fluss längs eines erweiternden Weges zu erhöhen, wie dies möglich ist:
Sei f = 0 der initiale Fluss;
repeat {
Suche bzgl. f einen erweiternden Weg von s nach t;
falls gefunden: erhöhe f längs dieses Weges;
} while möglich
Die Korrektheit dieses Algorithmus folgt unmittelbar aus dem folgenden Satz:
Sei ein Cut des Graphen definiert als eine Partition der Knotenmenge
in
und
, so dass gilt:
und
. Sei dann
. Die
Kapazität eines Cuts ist dann festgelegt durch
.
Daraus folgt unmittelbar der folgende Satz:
Sei ein Fluss der Größe
, sei
ein Cut von
Der Fluss ist also an jedem beliebigen Cut messbar. Aus diesem Satz folgt aber direkt:
Sei ein Fluss der Größe
, sei
ein Cut von
d.h. der Fluss ist höchstens so hoch wie die Kapazität eines Cuts.
Ist ein Fluss so groß wie die Kapazität eines Cuts
,
so ist
ein maximaler Fluss und
ist ein minimaler Cut
bezogen auf seine Kapazität c(S).
Wir betrachten nun folgende Situation:
Es gibt in keine erweiternden Wege mehr. Dann enden also alle von
ausgehenden erweiternden Wege - genauer gesagt deren Anfangsstücke -
entweder bei einer saturierten Vorwärtskante oder bei einer Rückwärtskante
mit Fluss 0. Durch diese Kanten wird also ein Cut
impliziert, dessen
Kapazität gleich dem momentanen Fluss ist. Daher muss der momentane Fluss
aufgrund des letzten Satzes maximal sein.
Die Suche nach einem erweiternden Weg wird durch eine Breitensuche
organisiert, die beim Knoten beginnt:
Markiere s;
Sei M := {s} die Menge der noch zu bearbeitenden Knoten;
while M nicht leer und t ist noch nicht markiert {
Besorge und entferne aus M einen markierten Knoten x
IF unmarkiertes y mit (x,y)
E und f(x,y)<c(x,y) THEN
markiere y und vermerke bei y seinen Vorgänger x;
notiere (x,y) := c(x,y) - f(x,y);
nimm y in M auf;
IF unmarkiertes y mit (y,x)
E und f(y,x) > 0 THEN
markiere y und vermerke bei y seinen Vorgänger x;
notiere (x,y) := f(y,x);
nimm y in M auf;
}
fallst t markiert THEN
berechne ausgehend von t längs der Vorgänger das maximal mögliche ;
erhöhe ausgehend von t längs der Vorgänger den Fluss f um ;
In folgendem Graph ist ein erweiternder Weg fett markiert. Er führt
von über
und
nach
und erlaubt eine Flusserhöhung um
.
Nach Anwendung des erweiternden Weges entsteht der folgende Graph, mit einem Fluss (und einem Cut) von 14 Einheiten. Da kein weiterer erweiternder Weg existiert, ist der Fluss maximal.
Zur effizienten Implementation der Breitensuche ist es erforderlich, bei jedem Knoten nicht nur die Liste seiner Nachfolger, sondern auch die Liste seiner Vorgänger zu speichern.