Autor: 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.
Beispiele für Flussnetze sind Wasserrohrsysteme, das Kabelssystem 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 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
 |  |
| Beispiel: Flussnetzwerk | Beispiel: 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 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.
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).
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)
