Maximale Flüsse WS13-14

Aus ProgrammingWiki

< AuK
Wechseln zu: Navigation, Suche
Autor: Yevgeniy Oliynyk

Inhaltsverzeichnis

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.

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

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

FlussnetzwerkFluss
Beispiel: FlussnetzwerkBeispiel: Fluss
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.

Sei $G = (V,E)$ ein Flussnetzwerk und $f$ ein Fluss in $G$. Dann gelten folgende 3 Gleichungen:

  1. Für alle $X \subseteq V$ gilt $f(X,X)=0$.
  2. Für alle $X,Y \subseteq V$ gilt $f(X,Y) = -f(Y,X)$.
  3. 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)$.


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.
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.
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:

Restnetzwerk
Beispiel: Restnetzwerk
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$.
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.

Erweitertungspfad
Beispiel: Erweiterungspfad
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.
$c_f(p) = $ min$\{ c_f(u,v):(u,v)$ ist eine Kante von $p\}$.
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.
Fluss(neu)Restnetzwerk(neu)
Beispiel: Fluss(neu)Beispiel: Restnetzwerk(neu)

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.

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.

Schnitt
Beispiel: Schnitt
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

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|$.

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

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

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:

  1. $f$ ist ein maximaler Fluss in $G$.
  2. Das Restnetzwerk $G_f$ enthält keine Erweiterungspfade.
  3. Es gilt $|f| = c(S,T)$ für einen Schnitt $(S,T)$ von $G$.

Der Basisalgorithmus von Ford und Fulkerson

Abarbeitung des Algorithmus am Beispiel (r. Restnetzwerk, l. Fluss)

Jede Iteration 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 aktualisiert (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.

Analyse

Die Laufzeit der Prozedur steht in Abhängigkeit 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.
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 eine einfacher Implementierung der Prozedur in Zeit $\mathcal{O}(E |f^*|)$. Dabei ist $f^*$ der durch den Algorithmus ermittelte maximale Fluss. Die ersten 3 Zeilen, die Initialisierung, benötigen eine Zeit in $\Theta(E)$. Die While-Schleife benötigt höchstens $|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)$.

Lösungen

1. Aufgabe

$$f(X,Y ) = \sum_{x\in X} \sum_{y\in Y} f(x,y)$$ $$= \sum_{x\in X} \sum_{y\in Y} -f(y,x)$$ $$= - \sum_{x\in X} \sum_{y\in Y} f(y,x)$$ $$= - \sum_{y\in Y} \sum_{x\in X} f(y,x)$$ $$= - f(Y,X)$$


2. Aufgabe

$$f(S,T) = f (S, V) - f (S, S)$$ $$= f (S, V) $$ $$= f (s, V) + f (S \setminus s, V) $$ $$= f (s, V) $$ $$= | f |$$


3. Aufgabe

Der Wert des maximalen Flusses beträgt 75. Ein möglicher Fluss wäre:

$f(s,v3) = 38$; $f(s,v4) = 37$; $f(v3,v5) = 38$; $f(v4,v9) = 22$; $f(v4,v5) = 15$; $f(v5,t) = 15$; $f(v5,v7) = 38$; $f(v9,v8) = 22$; $f(v8,v7) = 22$; $f(v7,t) = 60$ (nur positive Flüsse sind angegeben).

Quellen

Persönliche Werkzeuge