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

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.