Maximale Flüsse WS13-14
Inhaltsverzeichnis |
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 |