Algorithmus von Ford und Fulkerson

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder Abschnitt ist nicht allgemeinverständlich formuliert. Die Mängel sind unter Diskussion:Algorithmus von Ford und Fulkerson beschrieben. Wenn du diesen Baustein entfernst, begründe dies bitte auf der Artikeldiskussionsseite und ergänze den automatisch erstellten Projektseitenabschnitt Wikipedia:Unverständliche Artikel#Algorithmus von Ford und Fulkerson um {{Erledigt|1=~~~~}}.

Der Algorithmus von Ford und Fulkerson ist eine Methode auf dem Gebiet der algorithmischen Graphentheorie zur Bestimmung eines maximalen Flusses in einem Flussnetzwerk. Der Algorithmus wurde nach seinen Erfindern L.R. Ford Jr. und D.R. Fulkerson benannt.[1] Die Terminierung des Algorithmus ist gesichert, falls das Flussnetzwerk rationale Kapazitäten besitzt. Der Algorithmus besitzt jedoch eine superpolynomielle Worst-Case-Laufzeit. Weiterentwicklungen führten zum Edmonds-Karp-Algorithmus und dem Algorithmus von Dinic.

Der Algorithmus[Bearbeiten]

Gegeben sei ein Netzwerk N = (G,u,s,t), bestehend aus einem endlichen, gerichteten Graphen G=(V, E) mit einer Quelle  s \in V, einer Senke t \in V und einer Kapazitätsfunktion u\colon E \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\colon E \to\mathbb{R}_{\geq 0} mit den Eigenschaften

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

Hierbei bezeichnet \delta^+(x) die Menge der aus x hinausführenden Kanten und \delta^-(x) die Menge der in x hineinführenden Kanten. Der in einen Knoten eingehende Fluss muss also gleich dem ausgehenden Fluss sein.

Der Algorithmus sucht in jedem Schritt einen Weg von s nach t im Residualgraphen. Der Residualgraph G_f 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 mit f(e)>0 enthält E_{G_f} jeweils zusätzlich eine Rückkante \overleftarrow{e}=(w,v). Formal gilt also: G_f = (V, \{e\in E \mid f(e)<u(e)\}\dot{\cup} \{\overleftarrow{e} \mid \exists e\in E : e=(v,w) \ \and \ f(e)>0 \ \and \ \overleftarrow{e}=(w,v)\}) Dazu werden Residualkapazitäten u_f definiert, die jeder Kante e\in E 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 zuordnen, um wie viel der Fluss auf der zugehörigen Hinkante e\in E verringert werden kann. Also formal:

u_f(e) = \begin{cases}
u(e) - f(e) & \text{wenn } e\in E \\
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 ein beliebiger Fluss verwendet werden (auch der Nullfluss, der jeder Kante e den Wert 0 zuordnet). Der Algorithmus beschreibt sich wie folgt:

  1. (Initialisierung mit Nullfluss:) Setze f(e):=0 für jede Kante e\in E.
  2. Solange es im Residualgraphen G_f 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 setze: f(e):=f(e)+\gamma.
    Für alle \overleftarrow{e}\in E_W\setminus E setze für die zugehörige Hinkante e: f(e):=f(e)-\gamma.

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

Beispiel[Bearbeiten]

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 f_0((q,u))=f_0((q,v))=f_0((u,v))=f_0((u,s))=f_0((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 f_1((q,u))=f_1((u,v))=f_1((v,s))=3, es bleibt f_1((q,v))=f_1((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 f_2((q,u))=f_2((v,s))=3, f_2((u,v))=2 und f_2((q,v))=f_2((u,s))=1.

FF Beispiel 1 Pfad.svg
2. (b) Bilde das Residualnetzwerk N_{f_2}, worin der Fluss f_2 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 f_3((q,u))=f_3((v,s))=4, f_3((u,v))=3, und f_3((q,v))=f_3((u,s))=1.

FF Beispiel 2 Pfad.svg
3. (b) Bilde das Residualnetzwerk N_{f_3}; darin findet man den Fluss f_3 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 f_4 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 f_4 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[Bearbeiten]

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 N_f 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].

Laufzeit[Bearbeiten]

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[Bearbeiten]

 Commons: Algorithmus von Ford und Fulkerson – Sammlung von Bildern, Videos und Audiodateien

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. L.R. Ford Jr., D.R Fulkerson: Maximal flow through a network. In: Canad. J. Math.. 8, 1956, S. 399-404. doi:10.4153/CJM-1956-045-5.
  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).