TI

Versuchen wir mal "greedy", einen maximalen Fluss zu finden. Wir suchen einen Pfad von $s$ nach $t$, leiten dann entlang diesem soviel Fluss wie möglich und notieren uns dann für jede Kante, wieviel Kapazität übrig bleibt; bleibt keine mehr übrig, so löschen wir die Kante. Dann wiederholen wir alles.

In diesem Beispiel finden wir also einen Fluss vom Wert 6; dies ist allerdings nicht optimal, wie folgender, besserer Fluss zeigt:

Die Greedy-Methode ist also nicht optimal. Dafür ist sie natürlich erlaubt: sie findet einen legalen Fluss, nur nicht den optimalen. Bevor wir eine korrekte Methode entwickeln, die immer ein Optimum findet, nehmen wir uns die Zeit, die Greedy-Methode zu formalisieren.

Finde einen Pfad $p$ von $s$ nach $t$ im aktuellen Netzwerk $G :=(V, c, s, t)$.
Finde die Engpass-Kapazität $c_{\min} := \min_{e \in p} c(e) $.
Leite $c_{\min}$ Einheiten entlang des Pfades $p$; definiere also $f_p(e) := c_\min$ für alle $e \in p$ und $f_p(e) = 0$ für alle anderen Kanten.
Reduziere die Kapazitäten: $c(e) := c(e) - c_{\min}$ für alle Kanten $e$ entlang $p$.

Wir wiederholen diese Schritte, bis es keinen Pfad mehr von $s$ nach $t$ gibt. Argumentieren wir, warum es einen legalen Fluss findet. In Schritt 4 erzeugen wir ein neues Flussnetzwerk mit Restkapazitäten. Formal also $G' := (V, c', s,t)$ mit den neuen Kapazitäten $c'$, die wie folgt definiert sind:

$$ c'(e) := \begin{cases} c(e) - c_{\min} & \textnormal{ wenn $e \in p$} \\ c(e) & \textnormal{ sonst.} \end{cases} $$

Die entscheidende Beobachtung ist nun: wenn $f'$ ein Fluss in $G'$ ist, dann ist $f' + f_p$ ein Fluss in $G$. Wenn Sie die Schreibweise $f' + f_p$ verwirrt, dann denken Sie einfach daran, dass sowohl $f'$ als auch $f_p$ Funktionen $V \times V \rightarrow \R$ sind; solche Funktionen können wir punktweise aufaddieren. Diesen Schritt, nämlich zwei Flüsse aufzuaddieren, nennt man Augmentierung. Da in unserem Fall der eine Fluss $f_p$ entlang eines Pfades fließt, nennen wir $p$ einen augmentierenden Pfad. Unsere Methode ist also legal: durch das Aufaddieren erhalten wir einen legalen Fluss in $G$. Allerdings ist sie im Allgemeinen nicht optimal: es könnte einen Fluss $f^*$ in $G$ geben, den wir nicht in der Form $f' + f_p$ schreiben können. Wir demonstrieren diesen Fall noch einmal ein einem Beispiel, das weitaus einfacher ist als das obige. In dem folgenden Beispiel haben alle Kanten eine Kapazität von 1:

Das Residual-Netzwerk

Bleiben wir am Ball: wir wollen eine Methode/Regel, die uns erlaubt, einen bereits gefunden Fluss $f$ in $G$ zu erweitern; konkreter gesagt wollen wir, auf Basis von $f$, ein Residualnetzwerk $G' := (V,c',s,t)$ definieren, dass folgende Eigenschaft hat:

Legalität: jeder Fluss $f'$ in $G'$ soll uns einen Fluss $f' + f$ in $G$ geben.
Optimalität: für jeden Fluss $f^*$ in $G$ soll es einen Fluss $f'$ in $G'$ geben, so dass $f^* = f + f'$ gilt. In anderen Worten, jede Lösung in $G$ soll erreichbar bleiben.

Wir können das, was wir wollen, recht kurz und prägnant mathematisch ausdrücken. Wir definieren

$$ \flows(G) := \{ f : V \times V \rightarrow \R \ | \ f \textnormal{ ist ein Fluss in $G$ }\} \ . $$

Gegeben ein Fluss $f$ in $G$ wollen wir nun also ein Netzwerk $G' := (V,c',s,t)$ definieren, für das gilt

$$ \flows(G') = \{ f' : V \times V \rightarrow \R \ | \ f' + f \textnormal{ ist ein Fluss in $G$}\} \ . $$

Definition (Residualnetzwerk). Sei $f$ ein Fluss im Netzwerk $G = (V,c,s,t)$. Das Residualnetzwerk ist definiert als $G_f := (V,c_f,s,t) $ mit $c_f := c - f$.

Erinnern Sie sich: die Subtraktion von Funktionen wie im Ausdruck $c_f := c - f$ ist punktweise gemeint, also $c_f(u,v) := c(u,v) - f(u,v)$. Beachten Sie, dass $G_f$ tatsächlich ein Flussnetzwerk ist: alle Kapazitäten sind nicht-negativ, also $c_f(u,v) \geq 0$. Dies gilt, weil $f(u,v) \leq c(u,v)$ gilt, also weil $f$ ein Fluss in $G$ ist. Wenn $f$ die Kapazitätskonformität verletzen würde, so würde $G_f$ negative Kapazitäten aufweisen, was in diesem Kontext nicht erlaubt ist.

Lemma (Augmentierung im Residual-Netzwerk). Sei $f$ ein Fluss in $G = (V,c,s,t)$ und $G_f = (V,c-f, s,t)$ das Residualnetzwerk. Dann gilt

für jeden Fluss $f'$ in $G_f$ ist $f + f'$ ein Fluss in $G$;
jeder Fluss $f^*$ in $G$ lässt sich als $f^* = f + f'$ schreiben mit einem Fluss $f'$ in $G_f$.

Beweis. Punkt i haben wir bereits weiter oben diskutiert. Beweisen wir ihn hier aber noch einmal formal. Wir gehen einfach die Flussaxiome durch und stellen sicher, dass sie auch für die Summe $f + f'$ gelten.

Schiefsymmetrie. Die beiden Flüsse $f, f'$ sind nach Annehme schiefsymmetrisch. Also gilt $$ (f + f') (u,v) = f(u,v) + f'(u,v) = -f(v,u) - f'(v,u) = - (f + f') (v,u) \ . $$
Kapazitätskonformität. Der Fluss $f'$ erfüllt die Kapazitätskonformität im Residualnetzwerk $G_f = (V,c_f,s,t) = (V,c-f,s,t)$. Also gilt $f'(e) \leq c_f(e)) = c(e) - f(e) $ und somit $ (f + f') (e) \leq f(e) + c(e) - f(e) = c(e)$. Der augmentierte Fluss $f + f'$ erfüllt also die Kapazitätskonformität im Netzwerk $G$.
Flusserhalt. Sei $u \in V \setminus \{s,t\}$. Da $f$ und $f'$ Flüsse sind, gilt $\sum_{v} f(u,v) = 0 = \sum_{v} f'(u,v)$ und somit auch $\sum_v (f + f')(u,v) = 0$.

Schreiten wir nun weiter zu Punkt ii. Wir haben einen Fluss $f^*$ in $G$ und wollen zeigen, dass wir ihn als Summe $f^* = f + f'$ schreiben können, sodass $f'$ ein Fluss in $G_f$ ist. Hierfür kann es nur eine Lösung geben: $f' := f^* - f$. Damit ist natürlich sichergestellt, dass $f^* = f+f'$ gilt. Wir müssen nur noch zeigen, dass $f'$ auch wirklich ein Fluss in $G_f$ ist. Schiefsymmetrie und Flusserhalt zeigt man genauso wie für Punkt i. Um zu zeigen, dass $f'$ die Kapazitätskonformität für das Netzwerk $G_f$ erfüllt, rechnen wir

\begin{align} f'(u,v) & = f^*(u,v) - f(u,v) \\ & \leq c(u,v) - f(u,v) \\ & = c_f (u,v) \ . \end{align}

wobei die Ungleichung gilt, da $f^*$ selbst ein Fluss in $G$ und somit kapazitätskonform ist. $\square$

Ein Max-Fluss (oder Maxfluss) in einem Netzwerk ist ein Fluss mit maximalem Wert. Eine direkte und nützliche Konsequenz aus dem Lemma ist, dass es einen 1-zu-1-Zusammenhang gibt zwischen den Maxflüssen von $G$ und den Maxflüssen von $G_f$:

Korrolar Sei $G = (V,c,s,t)$ ein Flussnetzwerk, $f$ ein Fluss in $G$ und $G_f := (V, c-f, s,t)$ das Residualnetzwerk. Dann gilt

Wenn $f'$ ein Max-Fluss in $G_f$ ist, dann ist $f' + f$ ein Maxfluss in $G$.
Wenn $f^*$ ein Max-Fluss in $G$ ist, dann ist $f^* - f$ ein Maxfluss in $G_f$.

Daraus ergibt sich unmittelbar eine algorithmische Idee, um einen Maxfluss zu finden: finde einen Pfad $p$ von $s$ nach $t$; sei $f_p$ der Fluss, der soviel wie möglich entlang $p$ leitet, also \begin{align*} c_{\min} & := \min_{e \in p} c(e) \\ f_p(u,v) & := \begin{cases} c_\min & \textnormal{ wenn $(u,v) \in p$,}\\ - c_\min & \textnormal{ wenn $(v,u) \in p$,}\\ 0 & \textnormal{ sonst} \ . \end{cases} \end{align*} Dann machen wir iterativ weiter im Residualnetzwerk $G_f$. Dies ist als Ford-Fulkerson-Methode bekannt.

FordFulkerson (G, c, s, t):
f = 0 // der Fluss, der überal 0 ist
while (residual network G_f has path p from s to t ):
  f = f + f_p
return f

Theorem Wenn FordFulkerson terminiert, dann gibt es einen Maxfluss $f$ zurück.

Beweis. Sei $f$ der Fluss, den FordFulkerson zurückliefert. Streng genommen müssten wir erst einmal beweisen, dass es überhaupt ein Fluss ist. Aber das folgt unmittelbar aus dem Lemma: angenommen, $f$ ist am Anfang des Schleifendurchlaufs ein Fluss in $G$; weiterhin ist $f_p$ ein Fluss in $G_f$; daher ist der augmentierte Fluss $f + f_p$ ein Fluss in $G$.

Um zu zeigen, dass $f$ ein Maxfluss ist, nehmen wir irgendeinen anderen Fluss $f^*$ in $G$ und wollen zeigen, dass $\val(f) \geq \val(f^*)$ gilt. Aus dem Lemma folgt, dass sich $f^*$ als $f^* = f + f'$ schreiben lässt, wobei $f'$ ein Fluss in $G_f$ ist. Was aber ist $G_f$? Es ist das Residualnetzwerk zu dem Zeitpunkt, wo die while-Schleife abbricht. Es gibt in $G_f$ also keinen Pfad von $s$ nach $t$. Also kann es auch keinen Fluss mit positivem Wert geben. Was heißt das? Nun, dass $\val(f^* - f) \leq 0$ ist und somit $\val(f^*) \leq \val(f)$. $\square$

Wie Sie vielleicht schon bemerkt haben, habe ich obigen Code als Ford-Fulkerson-Methode und nicht Algorithmus bezeichnet. Zu einem Algorithmus fehlt ihr nämlich ein entscheidendes Merkmal: immer zu terminieren. Hier ist ein (nicht ganz legitimes) Beispiel, auf dem sie nicht terminiert:

Die Ausführung der Ford-Fulkerson-Methode in diesem Beispiel hat natürlich Pech: würde sie als augmentierenden Pfad den direkten Pfad von $s$ nach $t$ der Länge 2 nehmen, hätte sie schon nach einer Augmentierung festgestellt, dass es einen Fluss von Wert unendlich gibt. Allerdings haben wir in der Beschreibung der Methode offen gelassen, welcher Pfad für die Augmentierung verwendet werden soll; insofern dürfen "wir" im Worst-Case annehmen, dass immer der schlechteste Pfad gewählt wird. Allerdings ist das obige Beispiel kein richtiges Gegenbeispiel: wir haben ja $c: V \times V \rightarrow \R$ definiert, also sind unendlichen Kapazitäten gar nicht erlaubt. Interessanterweise gibt es ein weiteres Beispiel mit endlichen Kapazitäten, auf denen Ford-Fulkerson ebenfalls nicht terminiert, und noch schlimmer: der Wert des Flusses bleibt immer kleiner als 3, der Maxfluss hat aber Wert 2000.

Die Worst-Case-Ausführung von Ford-Fulkerson auf diesem Beispiel finden Sie in der pdf-Datei ford-fulkerson-pathological.pdf. Kernidee ist, dass, wenn Sie eine Zahlenfolge mit $a_0 := 1, a_1 := \varphi$ beginnen und dann für höhere Indices $a_i = a_{i-1} - a_{i-2}$ definieren, dann erhalten Sie eine Folge, deren Glieder immer kleiner werden, aber nie 0 erreichen. Dass $\varphi$, auch als goldener Schnitt bekannt, eine irrationale Zahl ist, ist ganz entscheidend, wie die beiden folgenden Übungen zeigen:

Übungsaufgabe Zeigen Sie, dass Ford-Fulkerson immer terminiert, wenn alle Kapazitäten ganze Zahlen sind.

Übungsaufgabe Zeigen Sie, dass Ford-Fulkerson immer terminiert, wenn alle Kapazitäten rationale Zahlen sind.

Es gibt noch eine weitere schlechte Nachricht: selbst wenn alle Kapazitäten ganze Zahlen sind, kann es sein, dass Ford-Fulkerson erst nach sehr langer Zeit terminiert. Das Beispiel haben Sie schon gesehen:

Der Maxfluss hat einen Wert von $2 \cdot 10^{100}$. Wenn Ford-Fulkerson jedoch Pech hat und immer den Weg durch die senkrechte Kante wählt, dann wächst der Wert des Flusses in jedem Schritt genau um 1. Man braucht dann also $2 \cdot 10^{100}$ Iterationen. Dies ist nicht effizient: wenn Sie $10^{100}$ durch $2^n$ ersetzen, sehen Sie, dass wir für das Speichern der Probleminstanz $\Theta(n)$ Bits brauchen, die Laufzeit aber $\Theta(2^n)$ ist, also exponentiell in der Bit-Größe der Input-Instanz.