Ford-Fulkerson-Algorithmus

Der Algorithmus von Ford und Fulkerson (nach seinen Erfindern Lester Randolph Ford junior und Delbert Ray Fulkerson^[1]) dient der Berechnung eines maximalen Flusses in einem Netzwerk. Er sucht sukzessive nach flussvergrößernden Pfaden, vergrößert den Fluss entlang dieser Pfade und hält an, falls kein solcher Pfad mehr existiert.

Algorithmus

Gegeben sei ein Netzwerk N = (V,E,q,s,c), bestehend aus einem endlichen gerichteten Graphen ohne Mehrfachkanten G = (V,E) mit einer Quelle $q\in V$, einer Senke $s\in V$ und einer Kapazitätsfunktion $c:E\to\mathbb{R}^+$, die jeder Kante (u,v) eine nicht-negative reelle Zahl c(u,v) als Kapazität zuordnet.

Der Algorithmus verändert in jedem Durchlauf einen Fluss im Netzwerk N, also eine Abbildung $f:E\to\mathbb{R}^+$ mit den Eigenschaften

• Kapazitätsbeschränkung: Für jede Kante (u,v) ist $0\le f(u,v)\le c(u,v)$.
• Flusserhaltung: Für jede Ecke $x\in V\setminus\{q,s\}$ gilt $\sum_{y\in V,(x,y)\in E}f((x,y))=\sum_{y\in V,(y,x)\in E}f((y,x))$.

Zur Initialisierung kann man den Nullfluss, der jeder Kante (u,v) den Wert 0 zuordnet, verwenden.

Ein Durchlauf des Algorithmus besteht aus folgenden Schritten:

1. Erweitere f auf umgekehrte Kanten durch f(v,u): = − f(u,v), und erweitere c durch c(v,u): = 0 falls c(u,v) > 0. Damit treten in der Regel als Werte von f auch negative Zahlen auf.
2. Bilde das Restnetzwerk N_f = (V,E_f,q,s,c_f) zum gegebenen Fluss f durch die Definition der Restkapazität c_f(u,v): = c(u,v) − f(u,v), für $(u,v)\in E$ oder $\quad (v,u)\in E$. Die Menge E_f besteht genau aus denjenigen Paaren $(u,v)\in V\times V$ mit c_f(u,v) > 0. Wegen des möglichen Auftretens negativer Werte von f kann das Restnetzwerk mehr oder andere Kanten besitzen als das ursprüngliche.
3. Suche im Restnetzwerk N_f einen Pfad W von der Quelle zur Senke, bei dem jede Kante eine positive Residualkapazität besitzt. Ein solcher Pfad wird flussvergrößernder oder augmentierender Pfad genannt. Falls kein solcher Pfad existiert, beende den Algorithmus mit f als Ausgabe.
4. Bestimme $\delta:=\min\{c_f(u,v): (u,v)\in W\}$.
5. Vergrößere den Fluss f entlang des flussvergrößernden Pfades W um δ durch f'(u,v): = f(u,v) + δ und f'(v,u): = f(v,u) − δ, für alle Kanten $(u,v)\in W$.

Beispiel

Gegeben sei ein Netzwerk mit vier Knoten q,u,v,s und den Kantengewichten 1, 2, 3, 4, 6 wie in der Grafik. Initialisiere den Fluss mit f0(q,u) = f0(q,v) = f0(u,v) = f0(u,s) = f0(v,s) = 0.
1. (a) Wähle irgendeinen Pfad von q nach s. Dieser Pfad (in der Grafik blau) hat die Kapazität 3, da dies die minimale Kantenkapazität der Kanten aus dem Pfad ist. Vergrößere den Fluss entlang des Pfades um 3, das ergibt f1(q,u) = f1(u,v) = f1(v,s) = 3, es bleibt f1(q,v) = f1(u,s) = 0, und die Erweiterung ergibt f1(u,q) = f1(v,u) = f1(s,v) = − 3.
1. (b) Bilde das Restnetzwerk $N_{f_0}$. Hier verringern sich die Kapazitäten der Kanten (q,u) und (v,s), die Kante (u,v) fällt weg, dafür kommen drei neue Kanten (u,q), (v,u) und (s,v) hinzu, die rot dargestellt sind. Man findet den Fluss f1 im Restnetzwerk durch Umkehrung der roten Kanten: Ist (x,y) eine rote Kante, so ist $(y,x)\in E$ und $f_1(y,x)=0-f_1(x,y)=c_{f_1}(x,y)$. Ist umgekehrt $(y,x)\in E$, ohne dass (x,y) eine rote Kante ist, so ist f1(y,x) = 0.
2. (a) Wähle irgendeinen Pfad von q nach s. Der in der Grafik blau gezeichnete Weg hat die minimale Kapazität 1. Vergrößere den Fluss zu f2(q,u) = f2(v,s) = 3, f2(u,v) = 2 und f2(q,v) = f2(u,s) = 1.
2. (b) Bilde das Restnetzwerk $N_{f_2}$, worin der Fluss f2 zu sehen ist.
3. (a) Wähle irgendeinen Pfad von q nach s. Der hier Gewählte (blau markiert) hat die Kapazität 1, also ist f3(q,u) = f3(v,s) = 4, f3(u,v) = 3, und f3(q,v) = f3(u,s) = 1.
3. (b) Bilde das Restnetzwerk $N_{f_3}$; darin findet man den Fluss f3 durch Umkehrung der roten Kanten.
4. (a) Wähle irgendeinen Pfad im Restnetzwerk $N_{f_3}$ von q nach s: In dieser Situation gibt es nur noch einen Pfad, nämlich (q,v,s). Es ergibt sich $f_4(q,u)=4,\quad f_4(q,v)=2,\quad f_4(u,v)=3,\quad f_4(u,s)=1,\quad f_4(v,s)=5$.
4. (b) Bilde das Restnetzwerk $N_{f_4}$. In q kommen nur noch Kanten an, es gibt also keinen Weg mehr von q nach s. Damit ist f4 ein maximaler Fluss durch das eingangs gegebene Netzwerk.

Ein maximaler Fluss im Beispielnetzwerk.

Der Algorithmus stoppt hier, da im verbliebenen Restnetzwerk kein Pfad von q nach s mehr existiert. Der erreichte Fluss ergibt sich, indem man zu jeder roten Kante ihre Zahl als Größe des Flusses auf der umgedrehten Kante nimmt. Die verbleibenden schwarzen Kanten geben die unbenutzten Restkapazitäten an.

Zur Effektivität des Algorithmus

Ford und Fulkerson konnten beweisen, dass ein Fluss f in einem Netzwerk N genau dann maximal ist, wenn es keinen augmentierenden Pfad gibt, d.h., wenn das Restnetzwerk N_f keinen Pfad von q nach s besitzt. Daher gilt:

Falls der Algorithmus von Ford und Fulkerson zum Stehen kommt, ist ein maximaler Fluss gefunden.

Dabei muss der maximale Fluss nicht eindeutig bestimmt sein.

Bei der Durchführung des Algorithmus vergrößert sich der betrachtete Fluss mit jedem Schritt. Daraus folgt eine wichtige Tatsache für ganzzahlige Netzwerke:

Sind alle Kapazitäten des gegebenen Netzwerks nicht-negative ganze Zahlen, so kommt der Algorithmus von Ford und Fulkerson nach endlich vielen Schritten zum Stehen und liefert einen maximalen Fluss, der außerdem ganzzahlig ist.

Sind alle Kapazitäten rationale Zahlen, so erhält man durch Multiplikation mit dem Hauptnenner ein ganzzahliges Netzwerk, und kann so die folgende Aussage beweisen:

Sind alle Kapazitäten des gegebenen Netzwerks nicht-negative rationale Zahlen, so kommt der Algorithmus von Ford und Fulkerson nach endlich vielen Schritten zum Stehen und liefert einen maximalen Fluss, der außerdem nur rationale Werte hat.

Falls irrationale Zahlen als Kapazitäten vorkommen, gilt das nicht mehr: Ford und Fulkerson konstruierten ein Beispiel eines Netzwerkes mit 10 Knoten und 48 Kanten, bei dem ihr Algorithmus bei geeigneter Auswahl der augmentierenden Pfade nicht zum Stehen kommt und auch nicht gegen einen maximalen Fluss konvergiert^[2]. Im Jahr 1995 fand Uri Zwick ein Beispiel mit 6 Knoten und 8 Kanten und einem derartigen Verhalten^[3].

Zeitkomplexität

Einerseits benötigt jeder Schleifendurchlauf des Algorithmus lediglich $\mathcal{O}(|V|)$ Zeit (siehe Landau-Notation), aber andererseits hängt die benötigte Anzahl der Schleifendurchläufe von der Größe der Kapazitäten ab. Es ist möglich, die flussvergrößernden Pfade sehr ungünstig zu wählen.

Wählt man in jedem Schritt immer den kürzesten augmentierenden Pfad zur Vergrößerung des Flusses, so erhält man den Algorithmus von Edmonds und Karp, der stets in höchstens $\mathcal{O}(|V| \cdot |E|^2)$ Schritten einen maximalen Fluss konstruiert. Eine weitere Verbesserung mit Hilfe zusätzlicher Techniken bringt der Algorithmus von Dinic mit einer (worst-case) Komplexität von $\mathcal{O}(|V|^2 \cdot |E|)$ Schritten.

Siehe auch

• Algorithmus von Edmonds und Karp, auch als Algorithmus von Dinic bekannt
• Flüsse und Schnitte in Netzwerken

Weblinks

• Ein sehr anschauliches Applet zu Ford-Fulkerson und Dijkstra.

Einzelnachweise

1. ↑ L. R. Ford and D. R. Fulkerson: Maximal flow through a network, Canad. J. Math. 8 (1956), 399-404.
2. ↑ L. R. Ford and D. R. Fulkerson: Flows in Networks, Princeton University Press 1962
3. ↑ Uri Zwick: The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate, Theoretical Computer Science 148, 165-170 (1995).