Algorithmus von Ford und Fulkerson

Der Algorithmus von Ford und Fulkerson ist ein Algorithmus aus dem mathematischen Teilgebiet der Graphentheorie zur Bestimmung eines maximalen Flusses in einem Flussnetzwerk mit rationalen Kapazitäten. Er wurde nach seinen Erfindern L.R. Ford Jr. und D.R. Fulkerson benannt.^[1] Die Anzahl der benötigten Operationen hängt vom Wert des maximalen Flusses ab und ist im Allgemeinen nicht polynomiell beschränkt. Weiterentwicklungen führten zum Algorithmus von Edmonds und Karp und dem Algorithmus von Dinic.

Wirkungsprinzip

Der Algorithmus beruht auf der Idee, einen Weg von der Quelle zur Senke zu finden, entlang dessen der Fluss weiter vergrößert werden kann, ohne die Kapazitätsbeschränkungen der Kanten zu verletzen. Ein solcher Weg wird auch als augmentierender Pfad bezeichnet. Durch Wiederholung können die Flüsse entlang mehrerer solcher Wege zu einem noch größeren Gesamt-Fluss zusammengefasst werden. Wird stets der kürzeste Weg gewählt, ergibt sich der Edmonds-Karp-Algorithmus.

Damit auf diese Weise tatsächlich stets der maximale Fluss gefunden werden kann, muss auch zugelassen werden, dass der Weg Kanten des Netzwerkes in umgekehrter Richtung folgt und für diese Kanten den Fluss wieder reduziert (sog. Rückkanten, s. u.). In der Analogie einer realen Flüssigkeitsbewegung bspw. durch ein Rohrleitungs-Netzwerk entspricht das der Idee, dass man anstatt einen Teil der durch eine Leitung fließenden Flüssigkeit wieder zurückzuschicken auch einfach von vornherein eine entsprechende Menge weniger durch diese Leitung schicken kann.

Formale Beschreibung

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

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

• Kapazitätsbeschränkung: Für jede Kante ${\displaystyle e}$ ist der Fluss durch ${\displaystyle 0\leq f(e)\leq c(e)}$ beschränkt.
• Flusserhaltung: Für jeden Knoten ${\displaystyle x\in V\setminus \{s,t\}}$ gilt:

  ${\displaystyle \sum _{e\in \delta ^{+}(x)}f(e)=\sum _{e\in \delta ^{-}(x)}f(e)}$.

Hierbei bezeichnet ${\displaystyle \delta ^{+}(x)}$ die Menge der aus ${\displaystyle x}$ hinausführenden Kanten und ${\displaystyle \delta ^{-}(x)}$ die Menge der in ${\displaystyle 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 ${\displaystyle s}$ nach ${\displaystyle t}$ im Residualgraphen. Der Residualgraph ${\displaystyle G_{f}}$ teilt sich mit ${\displaystyle G}$ dieselbe Knotenmenge und enthält die Kanten von ${\displaystyle G}$, die von ${\displaystyle f}$ nicht ausgelastet sind, ergänzt um sogenannte Rückkanten: Für jede Kante ${\displaystyle e=(v,w)\in E}$ mit ${\displaystyle f(e)>0}$ enthält ${\displaystyle E_{G_{f}}}$ jeweils zusätzlich eine Rückkante ${\displaystyle {\overleftarrow {e}}=(w,v)}$. Formal gilt also: ${\displaystyle G_{f}=(V,\{e\in E\mid f(e)<c(e)\}{\dot {\cup }}\{{\overleftarrow {e}}\mid \exists e\in E:e=(v,w)\ \land \ f(e)>0\ \land \ {\overleftarrow {e}}=(w,v)\})}$ Dazu werden Residualkapazitäten ${\displaystyle c_{f}}$ definiert, die jeder Kante ${\displaystyle e\in E}$ zuordnen, um wie viel der Fluss ${\displaystyle f}$ auf ${\displaystyle e}$ noch erhöht werden kann, und jeder Rückkante ${\displaystyle {\overleftarrow {e}}\in E_{G_{f}}\setminus E}$ zuordnen, um wie viel der Fluss auf der zugehörigen Hinkante ${\displaystyle e\in E}$ verringert werden kann. Also formal:

${\displaystyle c_{f}(e)={\begin{cases}c(e)-f(e)&{\text{wenn }}e\in E\\f(g)&{\text{wenn }}e={\overleftarrow {g}}{\text{ die Rückkante der Kante }}g{\text{ ist.}}\end{cases}}}$

Zur Initialisierung kann ein beliebiger Fluss verwendet werden (auch der Nullfluss, der jeder Kante ${\displaystyle e}$ den Wert 0 zuordnet). Der Algorithmus beschreibt sich wie folgt:

1. (Initialisierung mit Nullfluss:) Setze ${\displaystyle f(e):=0}$ für jede Kante ${\displaystyle e\in E}$.
2. Solange es im Residualgraphen ${\displaystyle G_{f}}$ einen Weg von ${\displaystyle s}$ nach ${\displaystyle t}$ gibt, bestimme einen solchen Weg ${\displaystyle W}$ und tue:

   Bestimme ${\displaystyle \gamma :=\min\{c_{f}(e)\mid e\in E_{W}\}}$.

   Für alle ${\displaystyle e\in E_{W}\cap E}$ setze: ${\displaystyle f(e):=f(e)+\gamma }$.

   Für alle ${\displaystyle {\overleftarrow {e}}\in E_{W}\setminus E}$ setze für die zugehörige Hinkante ${\displaystyle e}$: ${\displaystyle f(e):=f(e)-\gamma }$.

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

Beispiel

Beschreibung	Graph ${\displaystyle G}$ (mit Kapazitäten ${\displaystyle c}$)	Fluss ${\displaystyle f}$	Residualgraph ${\displaystyle G_{f}}$ (mit Residual-Kapazitäten ${\displaystyle c_{f}}$)
Wir betrachten das s-t-Flussnetzwerk ${\displaystyle N=(G,c,s,t)}$, bestehend aus dem Graphen ${\displaystyle G=(V,E)}$ mit vier Knoten ${\displaystyle V=\{s,t,u,v\}}$ und fünf Kanten ${\displaystyle E=\{su,ut,sv,vt,uv\}}$, der Quelle ${\displaystyle s\in V}$, der Senke ${\displaystyle t\in V}$ und der rechts angegebenen Kapazitätsfunktion ${\displaystyle c\colon E\to \mathbb {R} _{\geq 0}}$. Wir starten mit dem leeren Fluss ${\displaystyle f}$, der jeder Kante den Wert ${\displaystyle 0}$ zuordnet. Damit entspricht der Residualgraph ${\displaystyle G_{f}}$ zunächst genau dem Netz ${\displaystyle G}$ und die zugehörigen Residual-Kapazitäten ${\displaystyle c_{f}}$ genau den Kapazitäten ${\displaystyle c}$.	${\displaystyle e\in E}$ ${\displaystyle c(e)}$ su 4 ut 1 sv 2 vt 6 uv 3	${\displaystyle e\in E}$ ${\displaystyle f(e)}$ su 0 ut 0 sv 0 vt 0 uv 0	${\displaystyle e\in E}$ ${\displaystyle c_{f}(e)}$ ${\displaystyle c_{f}({\overleftarrow {e}})}$ su 4 ut 1 sv 2 vt 6 uv 3
Beschreibung	Augmentierender Pfad ${\displaystyle W}$ (mit Residual-Kapazitäten ${\displaystyle c_{f}}$)	Fluss ${\displaystyle f}$	Residualgraph ${\displaystyle G_{f}}$ (mit Residual-Kapazitäten ${\displaystyle c_{f}}$)
Nehmen wir an, der Algorithmus wählt als erstes den Pfad ${\displaystyle W=suvt}$, d. h. ${\displaystyle E_{W}=\{su,uv,vt\}}$ (blau). Entlang dieses Pfades können wir wegen ${\displaystyle c_{f}(uv)=3}$ den Fluss höchstens um ${\displaystyle 3}$ erhöhen (die mittlere Kante von oben nach unten). Daraus ergibt sich ein neuer Fluss (wir bezeichnen ihn wieder mit ${\displaystyle f}$) mit ${\displaystyle f(su)=f(uv)=f(vt)=3}$. Die Kante ${\displaystyle su}$ hat eine Kapazität von ${\displaystyle c(su)=4}$, wir nutzen davon im Moment jedoch nur ${\displaystyle f(su)=3}$. Im Residualgraphen bleibt die Kante daher mit einer Residualkapazität von ${\displaystyle c_{f}(su)=c(su)-f(su)=1}$ erhalten. Anders ist das beispielsweise mit der Kante ${\displaystyle uv}$, bei der keine Residualkapazität ${\displaystyle c_{f}(uv)=c(uv)-f(uv)=3-3=0}$ übrig bleibt. Sie „verschwindet“ deshalb aus dem Residualgraphen ${\displaystyle G_{f}}$ (grau gestrichelt dargestellt). Für die Kante ${\displaystyle vt}$ ergibt sich eine Residualkapazität von ${\displaystyle c_{f}(vt)=c(vt)-f(vt)=6-3=3}$. Weiterhin haben wir jetzt drei Kanten ${\displaystyle su,uv,vt}$ mit einem Fluss größer als Null. Diesen Fluss können wir theoretisch auch wieder „zurückschicken“, weshalb wir drei neue „Rückwärtskanten“ ${\displaystyle tv,vu,us}$ einführen, deren Residualkapazität genau dem aktuellen Fluss zwischen den beiden Knoten entspricht (rot).		${\displaystyle e\in E}$ ${\displaystyle f(e)}$ su 3 ut 0 sv 0 vt 3 uv 3	${\displaystyle e\in E}$ ${\displaystyle c_{f}(e)}$ ${\displaystyle c_{f}({\overleftarrow {e}})}$ su 1 3 ut 1 sv 2 vt 3 3 uv 3
Gehen wir davon aus, der Algorithmus wählt im nächsten Schritt den Pfad ${\displaystyle W=svut}$. Die maximale Flussvergrößerung entlang dieses Pfades ergibt sich aus der Residualkapazität ${\displaystyle c_{f}(ut)=c(ut)-f(ut)=1-0=1}$ der Kante ${\displaystyle ut}$. Dabei nutzen wir erstmals eine Rückwärtskante, die Kante ${\displaystyle vu}$. Während sich der Fluss f entlang der Kanten sv und ut um 1 erhöht, verringert sich der Fluss hingegen entlang der Kante uv um 1 von 3 auf 2. Damit ist die Kapazität ${\displaystyle c(uv)=3}$ dieser Kante nicht länger ausgenutzt, und die Kante uv kehrt in den Residualgraphen ${\displaystyle G_{f}}$ zurück, dieses Mal mit der Residualkapazität ${\displaystyle c_{f}(uv)=c(uv)-f(uv)=3-2=1}$. Dafür „verschwindet“ dieses Mal ut. Die Residualkapazität von sv verringert sich um 1 auf 1. Man beachte: alle Rückwärtskanten im Residualgraph haben wieder dieselbe Residualkapazität, die dem Wert des Flusses zwischen ihren beiden Knoten entspricht.		${\displaystyle e\in E}$ ${\displaystyle f(e)}$ su 3 ut 1 sv 1 vt 3 uv 2	${\displaystyle e\in E}$ ${\displaystyle c_{f}(e)}$ ${\displaystyle c_{f}({\overleftarrow {e}})}$ su 1 3 ut 1 sv 1 1 vt 3 3 uv 1 2
Als nächstes finde der Algorithmus z. B. erneut ${\displaystyle W=suvt}$. Dieses Mal lässt sich der Fluss entlang dieses Pfades lediglich noch um 1 erhöhen, gerade den Betrag, den wir im vorigen Schritt entlang der Kante uv wieder zurückgeschickt haben. Man merkt hier schon, dass der Algorithmus unter Umständen viel „hin und her“ schiebt, mehr dazu unter Laufzeit.		${\displaystyle e\in E}$ ${\displaystyle f(e)}$ su 4 ut 1 sv 1 vt 4 uv 3	${\displaystyle e\in E}$ ${\displaystyle c_{f}(e)}$ ${\displaystyle c_{f}({\overleftarrow {e}})}$ su 4 ut 1 sv 1 1 vt 2 4 uv 3
Im letzten Schritt kann nur noch der Pfad ${\displaystyle W=svt}$ gefunden werden. Dieser erhöht den Fluss nochmals um 1, für einen Gesamtwert des Flusses von ${\displaystyle 3+1+1+1=6}$. Das kann man auch gut daran erkennen, dass die von der Quelle s ausgehenden Kanten zusammen einen Fluss von ${\displaystyle f(su)+f(sv)=6}$ aufweisen, ebenso wie die in der Senke t endenden Kanten. Dieser Fluss ist tatsächlich maximal, was sich leicht daran erkennen lässt, dass alle Kanten, welche von der Quelle ausgehen, voll ausgelastet sind (diese beiden Kanten sind ein Flaschenhals, d. h. die Schnittkanten eines minimalen Schnitts). Der Algorithmus terminiert anschließend, da im sich ergebenden Residualgraphen kein Weg von s nach t mehr gefunden werden kann. Würde man den Algorithmus insofern ergänzen, dass er untersucht, welche Knoten von s noch erreichbar sind, ergäbe sich automatisch der o.a. minimale Schnitt, in diesem Fall enthält er lediglich den Knoten s, von dem man keinen anderen mehr erreichen kann (siehe Max-Flow-Min-Cut-Theorem).		${\displaystyle e\in E}$ ${\displaystyle f(e)}$ su 4 ut 1 sv 2 vt 5 uv 3	${\displaystyle e\in E}$ ${\displaystyle c_{f}(e)}$ ${\displaystyle c_{f}({\overleftarrow {e}})}$ su 4 ut 1 sv 2 vt 1 5 uv 3

Korrektheit

Ford und Fulkerson konnten beweisen, dass ein s-t-Fluss ${\displaystyle f}$ in einem Netzwerk ${\displaystyle N}$ genau dann maximal ist, wenn es keinen augmentierenden Pfad gibt, d. h., wenn das Restnetzwerk ${\displaystyle N_{f}}$ keinen Pfad von ${\displaystyle s}$ nach ${\displaystyle 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

Der Algorithmus von Ford und Fulkerson findet einen maximalen Fluss (sofern er terminiert) in ${\displaystyle {\mathcal {O}}(MN(|V(G)|+|E(G)|))}$ Rechenschritten (siehe Landau-Notation), wobei ${\displaystyle |V(G)|}$ die Anzahl der Knoten des Netzwerkes, ${\displaystyle |E(G)|}$ die Anzahl der Kanten des Netzwerkes, ${\displaystyle {\tfrac {M}{N}}}$ den Wert des maximalen Flusses und ${\displaystyle N}$ den Hauptnenner der Kapazitäten bezeichnen. Sind die Kantengewichte irrational, so kann es auftreten, dass der Algorithmus nicht terminiert^[4].

Beispiel für einen ungünstigen Graphen

Einerseits benötigt jeder Schleifendurchlauf des Algorithmus lediglich ${\displaystyle {\mathcal {O}}(|V(G)|+|E(G)|)}$ Operationen, 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. Das kann man sich am Beispiel links verdeutlichen: der Algorithmus kann in diesem Beispiel in jedem Schritt einen Weg über die mittlere Kante (ggf. als Rückwärtskante) wählen und den Gesamt-Fluss dadurch nur um 1 erhöhen.

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 ${\displaystyle {\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 ${\displaystyle {\mathcal {O}}(|V(G)|^{2}\cdot |E(G)|)}$.

Pseudocode

Eingabe: Ursprungsgraph
Ausgabe: Graph mit maximalem Fluss

Berechne Restgraph aus Ursprungsgraph
Solange es einen Erweiterungspfad im Restgraph gibt:
	Restkapazität = Minimum( Restkapazität der Kante für jede Kante des Erweiterungspfades )
	Für jede Kante des Erweiterungspfades:
		Falls Kante in Ursprungsgraph:
			Fluss( Kante ) = Fluss( Kante ) + Restkapazität
		Sonst:
			Fluss( umgekehrte Kante ) = Fluss( umgekehrte Kante ) - Restkapazität

Literatur

• Bernhard Korte, Jens Vygen: Kombinatorische Optimierung: Theorie und Algorithmen. Aus dem Englischen von Rabe von Randow. Springer-Verlag, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7

Weblinks

• Ein kommentierter Quellcode in C (Memento vom 25. Juni 2005 im Internet Archive) (englisch)
• Web Applet in Java – Algorithmus von Ford und Fulkerson an eigenen Graphen testen (englisch)

Einzelnachweise

1. L.R. Ford Jr., D.R Fulkerson: Maximal flow through a network. In: Canad. J. Math. 8. Jahrgang, 1956, S. 399–404, doi:10.4153/CJM-1956-045-5 (math.ca [PDF]). 
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).
4. KIT - Fakultät für Informatilk: An Even Worse Example for Ford Fulkerson. In: kit.edu. KIT, 30. Januar 2008, abgerufen am 25. Januar 2022 (englisch).