AuK/ Maximale Flüsse WS13-14

Wiki-Quelltext dieser Seite.

 '''Autor''': [mailto:s3yeoliy@stud.hszg.de Yevgeniy Oliynyk]

= Flussnetzwerk =

Bei einem Flussnetzwerk handelt es sich in der Praxis um Materialflüsse, bei dem ein Material von einer Quelle (Ausgangpunkt) zu einer Senke (Endpunkt) fließt. Der Fluss kann nur in bestimmten Kanälen, im Graph als Kanten dargestellt, entlang fließen. Außerdem können sich Kanäle kreuzen, wodurch mehrere Möglichkeiten für das Material entstehen, zur Senke zu gelangen. Diese Kreuzungen werden als Knoten dargestellt, wobei die Quelle und die Senke auch jeweils einen Knoten darstellen. Ausgehend davon, dass jeder Kanal nur eine begrenzte Kapazität aufweist, gilt es den Fluss optimal zu steuern. <br>

Beispiele für Flussnetze sind Wasserrohrsysteme, das Kabelsystem des Stromnetzwerks und das Straßensystem. <br>

Das Problem des maximalen Flusses versucht herauszufinden, was die maximale Flussrate in einem System ist, um das Material von der Quelle bis zur Senke zu transportieren und wie die Auslastungen der einzelnen Kanäle sind. Dabei muss jedoch sichergestellt sein, dass die Flusserhaltung eingehalten wird.

== Definition ==
=== Flussnetzwerk ===

Ein Flussnetzwerk wird durch einen Graph $G = (V,E)$ beschrieben, dessen Kanten gerichtet sind. Jede Kannte $(u,v) \in E$ weißt eine nicht negative Kapazität $c(u,v) \geq 0$ auf. In einem Flussnetzwerk liegt jeder Knoten $v \in V$ auf einem Pfad von der Quelle $s$ zur Senke $t$. Somit ist der Graph zusammenhängend.


=== Fluss ===

Ein Fluss in $G$ stellt eine reelwertige Funktion $f : V \times V → \mathbb{R}$ dar, die den Flusswert einer Kante beschreibt. Sie muss drei Bedingungen erfüllen:

* Kapazitätsbeschränkung: Für alle $u,v \in V$ gilt $f(u,v) \leq c(u,v)$.
* Asymmetrie: Für alle $u,v \in V$ gilt $f(u,v) = -f(v,u)$.
* Flusserhaltung: Für alle $u \in V \setminus \{s,t\}$ gilt $$\sum_{v \in V} f(u,v) = 0$$ Anders gesagt: die Menge, die in ein Knoten $v \in V \setminus \{s,t\}$ hineinfließt, muss auch wieder herausfließen.

=== Beispiel ===

<table>
<tr>
<td>[[Bild:Eugen_Bsp_definition_1.jpg|Flussnetzwerk]]</td><td>[[Bild:Eugen_Bsp_definition_2.jpg|Fluss]]</td>
</tr>
<tr style="text-align:center;">
<td>'''Beispiel: Flussnetzwerk'''</td><td>'''Beispiel: Fluss'''</td>
</tr>
<table>

Das Kantengewicht der Kante $u,v$ kennzeichnet die jeweilige Kapazität $c(u,v)$ im Flussnetzwerk. Im Fluss sind die Kanten als $f(u,v)/c(u,v)$ gekennzeichnet, wobei der Schrägstrich lediglich zur Trennung dient. Für den Fall, dass $f(u,v) \leq 0$ ist, wird nur die Kapazität angegeben.

== Netzwerk mit multiplen Quellen und Senken ==

Im Fall eines Netzwerks mit mehreren Quellen $\{ s_1,s_2,...,s_m \}$ und/oder Senken $\{ t_1,t_2,...,t_n \}$, werden sogenannte Superquellen bzw. Supersenken eingeführt. Dafür wird von der Superquelle für alle $i = 1,2,...,m$ eine gerichtete Kante $(s,s_1)$ eingefügt. Die Kapazität für diese Kanten ist $c(s,s_i)=\infty$. Genau so wird für alle $i = 1,2,...,n$ die gerichtete Kante $(t_i,t)$ mit der Kapazität $c(t_i,t) = \infty$ eingefügt. Damit wird erreicht, dass jede multiple Quelle mit dem gewünschten Fluss versorgt wird und der Fluss jeder multiplen Senke in die Supersenke münden kann.

== Arbeiten mit Flüssen ==

===Implizite Summennotation===

Da es verschiedene Funktionen gibt, deren Argumente 2 Knoten sind, wird eine implizite Summennotation verwendet. Beide Argumente können eine Menge von Knoten darstellen. Somit ist es möglich mit Mengen von Knoten zu arbeiten. Seien $X$ und $Y$ Mengen von Knoten, so würde gelten $$f(X,Y) = \sum_{x \in X}\sum_{y \in Y} f(x,y)$$ Die Bedingung zur Flusserhaltung kann nun mit $f(u,V) = 0$ für alle $u \in V \setminus \{s,t\}$ ausgedrückt werden. Ferner wird aus Gründen der Bequemlichkeit auf die geschweiften Klammern verzichtet, womit der Ausdruck $V\setminus s$ in der Gleichung $f(s,V\setminus s) = f(s,V)$ die selbe Bedeutung hat wie $V\setminus\{s\}$.

=== Lemma ===

Das Lemma macht gebrauch von der impliziten Summennotation und der Vereinfachung der Differenzmenge.
<div style="color:black; background-color:#DDDDDD; border:1px dotted midnightblue; padding-left:5px;">
Sei $G = (V,E)$ ein Flussnetzwerk und $f$ ein Fluss in $G$. Dann gelten folgende 3 Gleichungen:
# Für alle $X \subseteq V$ gilt $f(X,X)=0$.
# Für alle $X,Y \subseteq V$ gilt $f(X,Y) = -f(Y,X)$.
# Für alle $X,Y,Z \subseteq V$ mit $X \cap Y = \emptyset$ gilt $f(X \cup Y, Z) = f(X,Z)+f(Y,Z)$ und $f(Z, X \cup Y) = f(Z,X)+f(Z,Y)$.
</div>


<popup name = "Aufgabe 1">
Beweise unter Verwendung der 3 Bedingungen des [[AuK/_Maximale_Fl%C3%BCsse_WS13-14#Fluss|Flusses]] die Gültigkeit des 2. Teils des Lemmas.
</popup>

Dadurch ist es möglich $|f| = f(s,V) = f(V,t)$ zu beweisen. $|f|$ ist der Wert eines Flusses, also z.B. der gesamte Fluss aus der Quelle heraus.
Somit sieht der Beweis wie folgt aus:

$$| f | = f (s, V)$$
$$= f (V, V) − f (V \setminus s, V)$$
$$= − f (V \setminus s, V)$$
$$= f (V, V \setminus s)$$
$$= f (V, t) + f (V, V \setminus s,t)$$
$$= f (V, t)$$

= Die Ford-Fulkerson-Methode =

Diese Methode umfasst verschiedene Implementierungen mit unterschiedlichen Laufzeiten, weshalb sie nur als Methode und nicht als Algorithmus bezeichnet wird. Die Methode setzt sich aus 3 verschiedenen Ideen zusammen, die von Bedeutung sind für viele Flussalgorithmen und -probleme. <br>
Die Methode arbeitet iterativ und beginnt mit $f(u,v)=0$ für alle $u,v \in V$. Durch die Bestimmung eines Erweiterungspfades in jeder Iteration, wird der Flusswert erhöht. Dabei ist ein Erweiterungspfad nichts anderes als ein Pfad von der Quelle zur Senke, der noch über genügend freie Kapazität verfügt, sodass ein größerer Fluss darüber gesendet werden kann. Der Fluss wird dann entlang des Pfades erweitert und der gesamte Prozess wird so oft wiederholt, bis kein Erweiterungspfad mehr vorhanden ist. Als Ergebnis liefert die Methode einen maximalen Fluss.

''Ford-Fulkerson-Methode($G$,$s$,$t$)''
{|
 |
 1  initialisiere den Fluss $f$ mit 0
 2  '''while''' es existiert ein Erweiterungspfad $p$
 3      '''do''' verstärke den Fluss $f$ entlang $p$
 4  '''return''' $f$
|}

==Restnetzwerke==

Das Restnetzwerk besteht aus den Kanten, die weiteren Fluss aufnehmen können. Das äußert sich bei der Berechnung Restkapazität durch die Formel $$c_f(u,v)=c(u,v)-f(u,v)$$ Sollte $f(u,v)$ negativ sein und beispielsweise $-4$ betragen, so würde sich für $c_f(u,v)$ eine Restkapazität von $c(u,v) + 4$ ergeben und damit wäre die Restkapazität höher als die Kapazität. <br> Es lässt sich nun ein Restnetzwerk $G_f=(V,E_f)$ durch $$E_f=\{(u,v)\in V\times V:c_f(u,v) > 0\}$$ für ein vorhandenes Flussnetzwerk $G$ und einen vorhandenen Fluss $f$ angeben. Das bedeutet: Jede Kante von $G_f$ kann einen Fluss aufnehmen, der größer ist als null. Das Restnetzwerk zu dem Flussbeispiel von oben würde so aussehen:

<table>
<tr>
<td>[[Bild:Eugen_Bsp_restnetzwerk_3.jpg|Restnetzwerk]]</td>
</tr>
<tr style="text-align:center;">
<td>'''Beispiel: Restnetzwerk'''</td>
</tr>
<table>

Alle Kanten, die in $E_f$ vorkommen, stammen entweder aus $E$ oder es sind ihre Umkehrungen.
Wenn für eine Kante in $E$ die Ungleichung $f(u,v) < c(u,v)$ gilt, c_f(u,v) > 0 und $(u,v) \in E_f$. Das selbe Prinzip gilt für eine Kante in $E$, wo $f(u,v) > 0$ ist und somit $f(v,u) < 0$ folgt. Auch hier ist $c_f(v,u) > 0$ und damit $(v,u) \in E_f$. <br>
Man kann nun erkennen, dass das Restnetzwerk $G_f$ ebenfalls ein Flussnetzwerk ist. Dessen Kapazitäten werden durch $c_f$ ausgedrückt.

== Erweiterungspfade ==

Ein Erweiterungspfad $p$ ist ein Pfad im Restnetzwerk $G_f$ von $s$ nach $t$ zu einem gegebene Flussnetzwerk $G$ und einem Fluss $f$. Die Definition besagt, dass jede Kante $(u,v)$ eines Erweiterungspfades in der Lage ist einen zusätzlichen positiven Fluss von $u$ nach $v$ aufzunehmen. Dabei wird nicht die Kapazitätsbeschränkung der Kante verletzt. Im Beispiel, dass zuvor ein Restnetzwerk zeigte, ist nun ein Erweiterungspfad blau markiert.

<table>
<tr>
<td>[[Bild:Eugen_Bsp_erwpfad_4.jpg|Erweitertungspfad]]</td>
</tr>
<tr style="text-align:center;">
<td>'''Beispiel: Erweiterungspfad'''</td>
</tr>
<table>

Da $G_f$ als Flussnetzwerk aufgefasst wird, ist es möglich, ohne Kapazitätsbeschränkung zu überschreiten, den Fluss durch jede Kante entlang des Pfades zu erhöhen. Die Tatsache, dass $c_f(v2,v3)=4$ ist und somit die kleinste Restkapazität innerhalb dieses Pfades darstellt, erhöht sich der Fluss um bis zu vier Einheiten. Der maximale Betrag, um den man den Fluss durch jede Kante des Erweiterungspfades erhöhen kann, wird als Restkapazität von $p$ bezeichnet. <br>
$c_f(p) = $ min$\{ c_f(u,v):(u,v)$ ist eine Kante von $p\}$. <br>

Durch das Hinzufügen des Flusses, dass durch den Erweiterungspfad gefunden wurde, entsteht nun ein anderer Fluss in $G$, der näher am Maximum liegt und ein neues dazugehörendes Restnetzwerk.

<table>
<tr>
<td>[[Bild:Eugen_Bsp_fluss_5.jpg|Fluss(neu)]]</td><td>[[Bild:Eugen_Bsp_restnetzwerk_6.jpg|Restnetzwerk(neu)]]</td>
</tr>
<tr style="text-align:center;">
<td>'''Beispiel: Fluss(neu)'''</td><td>'''Beispiel: Restnetzwerk(neu)'''</td>
</tr>
<table>

== Schnitte von Flussnetzwerken ==

Um zu zeigen, dass durch die kontinuierliche Erweiterung des Flusses mithilfe von Restnetzwerken und Erweiterungspfaden ein maximaler Fluss entsteht, wird das maximaler-Fluss-minimaler-Schnitt-Theorem angewandt. Das Theorem besagt, dass ein Fluss genau dann maximal ist, sobald keine Erweiterungspfade mehr existieren. <br>

Durch den Schnitt $(S,T)$ eines Flussnetzwerk Partitionierung der Knotenmenge $V$ bewirkt wobei zwei neue Mengen $S$ und $T=V-S$ mit $s\in S$ und $t\in T$ entstehen. Bei der Annahme, dass $f$ ein Fluss ist, definiert sich der Nettofluss durch den Schnitt $(S,T)$ durch $f(S,T)$v und die Kapazität ist in dem Fall $c(S,T)$. Ein Schnitt, das die kleinste Kapazität von allen Schnitten eines Netzwerks darstellt, ist ein minimaler Schnitt.

<table>
<tr>
<td>[[Bild:Eugen_Bsp_schnitt_7.jpg|Schnitt]]</td>
</tr>
<tr style="text-align:center;">
<td>'''Beispiel: Schnitt'''</td>
</tr>
<table>

Der im Beispiel gezeigte Schnitt $(\{s,v1,v2\}\{v3,v4,t\})$ hat einen Nettofluss, der durch diesen Schnitt geht, von $$f(v1,v3)+f(v2,v3)+f(v2,v4)=12+(-4)+11$$ $$=19$$ und eine Kapazität von $$c(v1,v3)+c(v2,v4)=12+14$$ $$=26$$

Zu beachten ist, dass Flüsse, die von $T$ nach $S$ verlaufen und positiv sind, in der Berechnung des Nettoflusses subtrahiert werden müssen, während Kapazitäten, die durch ihren gerichteten Pfeil von $T$ nach $S$ verlaufen, nicht in die Berechnung der Kapazität des Schnitts mit eingehen dürfen.

Wie man nun leicht folgern kann, weist jeder Schnitt durch ein Flussnetzwerk mit einem Fluss denselben Nettofluss wie der Wert des Flusses auf. Das folgende Lemma unterstützt diese Aussage.

'''Lemma'''

<div style="color:black; background-color:#DDDDDD; border:1px dotted midnightblue; padding-left:5px;">
Seien $f$ ein Fluss in einem Flussnetzwerk $G$ mit der Quelle $s$ und der Senke $t$ und $(S,T)$ ein Schnitt von $G$. Dann gilt für den Nettofluss durch den Schnitt $f(S,T)=|f|$.
</div>

Wenn man beachtet, dass $f(S\setminus s, V) = 0$ wegen der Flusserhaltung gilt, kann man das Lemma ähnlich wie schon das vorhergehende Beweisen.

<popup name = "Aufgabe 2">
Beweise unter Verwendung des oberen [[AuK/_Maximale_Fl%C3%BCsse_WS13-14#Lemma|Lemmas]], dass $f(S,T)=|f|$ gilt.
</popup>

Schaut man sich die Eigenschaften des Schnitts an, so wird deutlich, dass ein Fluss $f$ in einem Flussnetzwerk $G$ nach oben beschränkt ist, und dass durch die Kapazität jedes beliebigen Schnitts. Zur Veranschaulichung: $$|f| = f(S,T)$$ $$=\sum_{u\in S}\sum_{v\in T}f(u,v)$$ $$\leq\sum_{u\in S}\sum_{v\in T}c(u,v)$$ $$=c(S,T)$$
Das Theorem sagt also aus, dass der Wert eines maximalen Flusses offensichtlich gleich der Kapazität eines minimalen Schnitts ist.

'''Theorem'''

<div style="color:black; background-color:#DDDDDD; border:1px dotted midnightblue; padding-left:5px;">
Wenn $f$ ein Fluss in einem Flussnetzwerk $G=(V,E)$ mit der Quelle $s$ und der Senke $t$ ist, dann sind die folgenden Bedingungen äquivalent:
# $f$ ist ein maximaler Fluss in $G$.
# Das Restnetzwerk $G_f$ enthält keine Erweiterungspfade.
# Es gilt $|f| = c(S,T)$ für einen Schnitt $(S,T)$ von $G$.
</div>

== Der Basisalgorithmus von Ford und Fulkerson ==

[[Bild:Eugen_Bsp_loesung_8.PNG|right|thumb|300px|Abarbeitung des Algrorithmus am Beispiel (r. Restnetzwerk, l. Fluss)]]

Jede Iteartion der Ford-Fulkerson-Methode liefert einen Erweiterungspfad $p$ und erhöht jede Kante des Pfades den Fluss $f$ um die Restkapazität $c_f(p)$.

=== Algorithmus ===

''Ford-Fulkerson($G$,$s$,$t$)''
{|
 |
 1  '''for''' alle Kanten $(u,v) \in E[G]$
 2      '''do''' $f[u,v] ← 0$
 3         $f[v,u] ← 0$
 4  '''while''' es existiert ein Pfad $p$ von $s$ nach $t$ im Restnetzwerk $G_f$
 5      '''do''' $c_f(p) ←$ min$\{c_f(u,v):(u,v$ gehört zu $p\}$
 6         '''for''' alle Kanten $(u,v)$ von $p$
 7             '''do''' $f[u,v] ← f[u,v]+c_f(p)$
 8                $f[v,u] ← -f[u,v]$
|}

Als erstes wird ein Fluss mit dem Wert 0 initialisiert (Zeile 1 bis 3). Dann wird solange iteriert, bis kein Erweiterungspfad im Restnetzwerk vorhanden ist (Zeile 4). Wenn ein Pfad gefunden wird, so wird dessen Restkapazität berechnet (Zeile 5) und anschließend der Fluss aktualiesiert (Zeile 6 bis 8). Sobald die Bedingung der While-Schleife nicht mehr erfüllt ist, befindet sich in $f$ der maximale Fluss des gegebenen Flussnetzwerks.

<popup name = "Aufgabe 3">
Finde einen maximalen Fluss im Flussnetzwerk. <br>
Welchen Wert hat der Fluss? <br>
[[Bild:Eugen_Uebung.jpg|800px]]
</popup>

=== Analyse ===

Die Laufzeit der Prozedur steht in Abhängikeit mit der Bestimmung des Erweiterungspfades. Eine schlechte Wahl kann unter umständen dazu führen, dass der Algorithmus nicht terminiert und der Wert des Flusses nicht wie gewünscht gegen den Wert des maximalen Flusses konvergiert. Dieser Fall kann jedoch nur dann eintreten, wenn die Kantenkapazitäten irrationale Zahlen sind. Wird der Erweiterungspfad beispielsweise mit Hilfe der Breitensuche bestimmt, läuft der Algorithmus in polynomialer Zeit. <br>
Für die Analyse werden ganzzahlige Kapazitäten vorausgesetzt. Im Falle von rationalen Zahlen, kann eine geeignete Skalentransformation durchgeführt werden. Unter den Bedingungen läuft läuft eine einfacher Implementierung der Prozedur in Zeit $\mathcal{O}(E |f^*|)$. Dabei ist $f^*$ der durch den Algorithmus ermittelte maximale Fluss. Die erste 3 Zeilen, die Initialisierung, benötigen eine Zeit in $\Theta(E)$. Die While-Schleife benötigt höhstens $|f^*|$ Durchläufe, da sich in jeder Iteration der Wert des Flusses um mindestens eine Einheit erhöht.

=== Der Edmonds-Karp-Algorithmus ===

Im Vergleich zum Algorithmus von Ford und Fulkerson, ist dieser Algorithmus besser, was die Schranke angeht. Dabei unterscheiden sie sich nur in der 4. Zeile, denn der Edmonds-Karp-Algorithmus sucht nach einem Erweiterungspfad mit dem Prinzip der Breitensuche. Die Zeit beläuft sich somit in $\mathcal{O}(VE^2)$.

= Weitere Methoden =

= Lösungen =

Die Lösungen werden nach der Veranstaltung veröffentlicht.

= Quellen =

* Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung,Oldenbourg Verlag, 2007
* Vöcking, Berthold: Taschenbuch der Algorithmen, Springer-Verlag, 2008
* http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS1011/AuD/nosec/ad_v15.pdf