Algorithmus von Ford und Fulkerson

Der Algorithmus von Ford und Fulkerson (nach seinen Erfindern Lester Randolph Ford junior und Delbert Ray Fulkerson[1]) dient der Berechnung eines maximalen s-t-Flusses in einem Netzwerk. Er sucht sukzessiv nach flussvergrößernden Pfaden im Residualgraphen (Restnetz), vergrößert den Fluss entlang dieser Pfade und hält an, falls kein solcher Pfad mehr existiert. Wenn die Kapazitäten der Kanten irrationale Zahlen sind, kann es sein, dass der Algorithmus nicht konvergiert. Außerdem kann der Algorithmus, bei ungeschickter Verteilung der Kapazitäten, eine schlechte Laufzeit haben. Er dient als Grundlage für den besseren Edmonds-Karp-Algorithmus.

Inhaltsverzeichnis

Der Algorithmus

Gegeben sei ein Netzwerk N = (G,u,s,t), bestehend aus einem endlichen, gerichteten Graphen G = (V(G),E(G)) mit einer Quelle  s\in V(G), einer Senke t\in V(G) und einer Kapazitätsfunktion u:E(G)\to\mathbb{R}_{\geq 0}, die jeder Kante e eine nichtnegative reelle Zahl u(e) als Kapazität zuordnet.

Der Algorithmus verändert in jedem Durchlauf einen s-t-Fluss im Netzwerk N, also eine Abbildung f:E(G)\to\mathbb{R}_{\geq 0} mit den Eigenschaften

  • Kapazitätsbeschränkung: Für jede Kante e ist 0\le f(e)\le u(e).
  • Flusserhaltung: Für jeden Knoten x\in V(G)\setminus\{s,t\} gilt:
    \sum_{e\in \delta^+(x)}f(e)=\sum_{e\in \delta^-(x)}f(e).

Hierbei bezeichnet δ + (x) die Menge der aus x hinausführenden Kanten und δ (x) die Menge der in x hineinführenden Kanten.

Der Algorithmus sucht in jedem Schritt einen Weg von s nach t im Residualgraphen. Der Residualgraph Gf teilt sich mit G dieselbe Knotenmenge und enthält die Kanten von G, die von f nicht ausgelastet sind, ergänzt um sogenannte Rückkanten: Für jede Kante e=(v, w)\in E(G) mit f(e) > 0 enthält E(Gf) jeweils zusätzlich eine Rückkante \overleftarrow{e}=(w,v). Formal gilt also: G_f = (V(G), \{e\in E(G) \mid f(e)<u(e)\}\dot{\cup} \{\overleftarrow{e} \mid \exists e\in E(G): e=(v,w) \ \and \ f(e)>0 \ \and \ \overleftarrow{e}=(w,v)\}) Dazu werden Residualkapazitäten uf definiert, die jeder Kante e\in E(G) zuordnen, um wie viel der Fluss f auf e noch erhöht werden kann, und jeder Rückkante \overleftarrow{e}\in E(G_f)\setminus E(G) zuordnen, um wie viel der Fluss auf der zugehörigen Hinkante e\in E(G) verringert werden kann. Also formal:

u_f(e) = \begin{cases}
u(e) - f(e) & \text{wenn } e\in E(G) \\
f(g) & \text{wenn } e=\overleftarrow{g} \text{ die R}\mathrm{\ddot u}\text{ckkante der Kante } g \text{ ist.} 
\end{cases}

Zur Initialisierung kann man den Nullfluss, der jeder Kante e den Wert 0 zuordnet, verwenden. Der Algorithmus beschreibt sich wie folgt:

  1. (Initialisierung:) Setze f(e): = 0 für jede Kante e\in E(G).
  2. Solange es im Residualgraphen Gf einen Weg von s nach t gibt, bestimme einen solchen Weg W und tue:
    Bestimme \gamma:=\min\{u_f(e) \mid e\in E(W)\}.
    Für alle e\in E(W)\cap E(G) setze: f(e): = f(e) + γ.
    Für alle \overleftarrow{e}\in E(W)\setminus E(G) setze für die zugehörige Hinkante e: f(e): = f(e) − γ.

Sind alle Kapazitäten rational, berechnet der Algorithmus nach endlich vielen Schritten einen maximalen s-t-Fluss.

Beispiel

Gegeben sei ein Netzwerk mit vier Knoten q,u,v,s und den Kapazitäten 1, 2, 3, 4, 6 wie in der Grafik. Gesucht ist ein maximaler q-s-Fluss.

Initialisiere den Fluss mit f0((q,u)) = f0((q,v)) = f0((u,v)) = f0((u,s)) = f0((v,s)) = 0.

FF Beispiel 0.svg
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 auf dem Pfad ist.

Vergrößere den Fluss entlang des Pfades um 3, dies ergibt f1((q,u)) = f1((u,v)) = f1((v,s)) = 3, es bleibt f1((q,v)) = f1((u,s)) = 0.

FF Beispiel 0 Pfad.svg
1. (b) Bilde das Residualnetzwerk 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 Rückkanten (u,q), (v,u) und (s,v) hinzu, die rot dargestellt sind. Auf diesen ergeben sich die Residualkapazitäten u_{f_1}((u,q))=u_{f_1}((v,u))=u_{f_1}((s,v))=3.
FF Beispiel 1.svg
2. (a) Wähle irgendeinen Pfad von q nach s im Residualnetzwerk. Der in der Grafik blau gezeichnete Weg hat die minimale Kapazität 1.

Vergrößere den Fluss entlang des Pfades um eins, dies ergibt f2((q,u)) = f2((v,s)) = 3, f2((u,v)) = 2 und f2((q,v)) = f2((u,s)) = 1.

FF Beispiel 1 Pfad.svg
2. (b) Bilde das Residualnetzwerk N_{f_2}, worin der Fluss f2 zu sehen ist. Die Kapazität der Kante (q,v) verringert sich um eins und eine neue Rückkante (v,q) wird gebildet. Die Kapazität der Kante (u,v) erhöht sich um eins, so dass die Hinkante (u,v) wieder entsteht. Die Kapazität der Kante (u,s) wird um eins verringert, wodurch die Hinkante (u,s) entfernt wird. Es ergeben sich die Residualkapazitäten  u_f((v,q))=u_f((s,u))=1,\ u_f((v,u))=2,\ u_f((u,q))=u_f((s,v))=3
FF Beispiel 2.svg
3. (a) Wähle irgendeinen Pfad von q nach s im Residualnetzwerk.

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.

FF Beispiel 2 Pfad.svg
3. (b) Bilde das Residualnetzwerk N_{f_3}; darin findet man den Fluss f3 durch Umkehrung der roten Kanten.
FF Beispiel 3.svg
4. (a) Wähle irgendeinen Pfad im Residualnetzwerk N_{f_3} von q nach s: In dieser Situation gibt es nur noch einen Pfad, nämlich (q,v,s). Dieser hat die minimale Kapazität eins.

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.

FF Beispiel 3 Pfad.svg
4. (b) Bilde das Residualnetzwerk 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.
FF Beispiel 4.svg
Ein maximaler Fluss im Beispielnetzwerk

Der Algorithmus stoppt hier, da im verbliebenen Residualnetzwerk kein Pfad von q nach s mehr existiert. Den erreichten Fluss f4 sieht man, 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 Residualkapazitäten an.

Zur Korrektheit des Algorithmus

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

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

Dabei muss der maximale s-t-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 nichtnegative ganze Zahlen, so kommt der Algorithmus von Ford und Fulkerson nach endlich vielen Schritten zum Stehen und liefert einen maximalen s-t-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 nichtnegative rationale Zahlen, so kommt der Algorithmus von Ford und Fulkerson nach endlich vielen Schritten zum Stehen und liefert einen maximalen s-t-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(G)|+|E(G)|) 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 einen kürzesten augmentierenden Pfad zur Vergrößerung des Flusses, so erhält man den Algorithmus von Edmonds und Karp, der stets in Laufzeit  \mathcal{O}(|V(G)| \cdot |E(G)|^2) einen maximalen s-t-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(G)|^2 \cdot |E(G)|) .

Weblinks

 Commons: Ford-Fulkerson's algorithm – Sammlung von Bildern, Videos und Audiodateien

Quellen

Einzelnachweise

  1. Lester Randolph Ford junior, Delbert Ray Fulkerson: Maximal flow through a network, Canad. J. Math. 8 (1956), 399-404.
  2. Lester Randolph Ford junior, Delbert Ray 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).

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus von Bellman und Ford — Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.… …   Deutsch Wikipedia

  • Algorithmus von Edmonds und Karp — Der Edmonds Karp Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung der Ford Fulkerson Methode zur Berechnung des maximalen s t Flusses in Netzwerken mit positiven reellen Kapazitäten. Sie verwendet den jeweils… …   Deutsch Wikipedia

  • Ford (Begriffsklärung) — Ford steht für Ford, eine geschützte Marke des Automobilkonzerns Ford Motor Company Ford (Familienname), einen Familiennamen, siehe auch dort für bekannte Namensträger Ford Foundation, amerikanische Stiftung Ford Models, amerikanische… …   Deutsch Wikipedia

  • 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 …   Deutsch Wikipedia

  • Flüsse und Schnitte in Netzwerken — sind Strukturen der Graphentheorie, die vielfältige Anwendungen finden. Inhaltsverzeichnis 1 Definitionen, wichtige Begriffe und Eigenschaften 1.1 Netzwerk 1.2 Fluss 1.2.1 …   Deutsch Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

  • Lester Randolph Ford junior — (* 23. September 1927 in Houston) ist ein US amerikanischer Mathematiker und Sohn von Lester Randolph Ford senior[1]. Zusammen mit Delbert Ray Fulkerson entwickelte er den Algorithmus von Ford und Fulkerson und gemeinsam mit Richard Bellman den… …   Deutsch Wikipedia

  • Bellman-Ford-Moore-Algorithmus — Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.… …   Deutsch Wikipedia

  • Bellmann-Ford — Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.… …   Deutsch Wikipedia

  • Moore-Bellman-Ford-Algorithmus — Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”