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, das jeder Kanal nur eine begrenzte Kapazität aufweißt, gilt es den Fluss optimal zu steuern. <br>

Beispiele für Flussnetze sind Wasserrohrsysteme, das Kabelssystem 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 3 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 gewunschten Fluss versorgt wird und der Fluss jeder multiplen Senke in die Supersenke münden kann.

== Arbeiten mit Flüssen ==

===Impliziete 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 Summmennotation 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>

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 Flussnetztwerk $G$ und einem Fluss $f$.