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

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\}.