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.

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:

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)

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: