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. 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 $N=(G,c,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 $c:E\to {ℝ}_{\ge 0}$, die jeder Kante $e$ eine nichtnegative reelle Zahl $c(e)$ als Kapazität zuordnet.

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

• Kapazitätsbeschränkung: Für jede Kante $e$ ist der Fluss durch $0\le f(e)\le c(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)<c(e)\}\dot{\cup }\{\overleftarrow{e}\mid \mathrm{\exists }e\in E:e=(v,w)\wedge f(e)>0\wedge \overleftarrow{e}=(w,v)\})$ Dazu werden Residualkapazitäten $c_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:

$c_f(e)=\{\begin{array}{cc}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{array}$

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 \{c_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

Beschreibung	Graph $G$ (mit Kapazitäten $c$)	Fluss $f$	Residualgraph $G_f$ (mit Residual-Kapazitäten $c_f$)
Wir betrachten das s-t-Flussnetzwerk $N=(G,c,s,t)$, bestehend aus dem Graphen $G=(V,E)$ mit vier Knoten $V=\{s,t,u,v\}$ und fünf Kanten $E=\{su,ut,sv,vt,uv\}$, der Quelle $s\in V$, der Senke $t\in V$ und der rechts angegebenen Kapazitätsfunktion $c:E\to {ℝ}_{\ge 0}$. Wir starten mit dem leeren Fluss $f$, der jeder Kante den Wert $0$ zuordnet. Damit entspricht der Residualgraph $G_f$ zunächst genau dem Netz $G$ und die zugehörigen Residual-Kapazitäten $c_f$ genau den Kapazitäten $c$.	Datei:Fordfulk-residual-0.svg $e\in E$ $c(e)$ su 4 ut 1 sv 2 vt 6 uv 3	Datei:Fordfulk-flow-0.svg $e\in E$ $f(e)$ su 0 ut 0 sv 0 vt 0 uv 0	Datei:Fordfulk-residual-0.svg $e\in E$ $c_f(e)$ $c_f(\overleftarrow{e})$ su 4 ut 1 sv 2 vt 6 uv 3
Beschreibung	Augmentierender Pfad $W$ (mit Residual-Kapazitäten $c_f$)	Fluss $f$	Residualgraph $G_f$ (mit Residual-Kapazitäten $c_f$)
Nehmen wir an, der Algorithmus wählt als erstes den Pfad $W=suvt$, d. h. $E_W=\{su,uv,vt\}$ (blau). Entlang dieses Pfades können wir wegen $c_f(uv)=3$ den Fluss höchstens um $3$ erhöhen (die mittlere Kante von oben nach unten). Daraus ergibt sich ein neuer Fluss (wir bezeichnen ihn wieder mit $f$) mit $f(su)=f(uv)=f(vt)=3$. Die Kante $su$ hat eine Kapazität von $c(su)=4$, wir nutzen davon im Moment jedoch nur $f(su)=3$. Im Residualgraphen bleibt die Kante daher mit einer Residualkapazität von $c_f(su)=c(su)-f(su)=1$ erhalten. Anders ist das beispielsweise mit der Kante $uv$, bei der keine Residualkapazität $c_f(uv)=c(uv)-f(uv)=3-3=0$ übrig bleibt. Sie „verschwindet“ deshalb aus dem Residualgraphen $G_f$ (grau gestrichelt dargestellt). Für die Kante $vt$ ergibt sich eine Residualkapazität von $c_f(vt)=c(vt)-f(vt)=6-3=3$. Weiterhin haben wir jetzt drei Kanten $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“ $tv,vu,us$ einführen, deren Residualkapazität genau dem aktuellen Fluss zwischen den beiden Knoten entspricht (rot).		$e\in E$ $f(e)$ su 3 ut 0 sv 0 vt 3 uv 3	$e\in E$ $c_f(e)$ $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 $W=svut$. Die maximale Flussvergrößerung entlang dieses Pfades ergibt sich aus der Residualkapazität $c_f(ut)=c(ut)-f(ut)=1-0=1$ der Kante $ut$. Dabei nutzen wir erstmals eine Rückwärtskante, die Kante $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 $c(uv)=3$ dieser Kante nicht länger ausgenutzt, und die Kante uv kehrt in den Residualgraphen $G_f$ zurück, dieses Mal mit der Residualkapazität $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.	Datei:Fordfulk-path-2.svg	Datei:Fordfulk-flow-2.svg $e\in E$ $f(e)$ su 3 ut 1 sv 1 vt 3 uv 2	Datei:Fordfulk-residual-2.svg $e\in E$ $c_f(e)$ $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 $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.		Datei:Fordfulk-flow-3.svg $e\in E$ $f(e)$ su 4 ut 1 sv 1 vt 4 uv 3	$e\in E$ $c_f(e)$ $c_f(\overleftarrow{e})$ su 4 ut 1 sv 1 1 vt 2 4 uv 3
Im letzten Schritt kann nur noch der Pfad $W=svt$ gefunden werden. Dieser erhöht den Fluss nochmals um 1, für einen Gesamtwert des Flusses von $3+1+1+1=6$. Das kann man auch gut daran erkennen, dass die von der Quelle s ausgehenden Kanten zusammen einen Fluss von $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).		Fehler beim Erstellen des Vorschaubildes: $e\in E$ $f(e)$ su 4 ut 1 sv 2 vt 5 uv 3	Datei:Fordfulk-residual-4.svg $e\in E$ $c_f(e)$ $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 $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. Im Jahr 1995 fand Uri Zwick ein Beispiel mit 6 Knoten und 8 Kanten und einem derartigen Verhalten.

Laufzeit

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

Datei:Ford-Fulkerson example 1.svg

Beispiel für einen ungünstigen Graphen

Einerseits benötigt jeder Schleifendurchlauf des Algorithmus lediglich $𝒪(|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 $𝒪(|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 $𝒪(|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

• Vorlage:Literatur

Weblinks

• Vorlage:Webarchiv (englisch)
• Vorlage:Internetquelle