Kurs:Algorithmen und Datenstrukturen/Vorlesung/Flussproblem

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Flussproblem

Auf dieser Seite wird das Flussproblem behandelt. Die Bestimmung des maximalen Flusses muss in vielen logischen Aufgaben angewandt werden. Beispielsweise bei Verteilungsnetzen mit Kapazitäten wie Wasserrohren, Förderbändern oder Paketvermittlungen mit Rechnernetzen. Die Quellen liefert beliebig viele Objekte pro Zeiteinheit und die Senke verbraucht diese. Jede Verbindung hat eine maximale Kapazität c und einen aktuellen Fluss f. Wie hoch ist nun die Übertragungskapazität?

Definition Fluss

Ein Fluss f von $q\in V$ nach $z\in V$ ist eine Funktion $f_{q,z}:E\to \mathbb {R}$. Für diese Funktion $f_{q,z}$ gelten folgende zwei Bedingungen:

1. Die Kapazitäten werden eingehalten: $\forall e\in E:f_{q,z}(e)\leq c(e)$
2. Was in einen Knoten hereinfließt, muss wieder herausfließen, mit Ausnahme von q und z: $\forall v\in V\backslash \{q,z\}:\sum _{u\in P(v)}f((u,v))=\sum _{w\in S(v)}f((v,w))$, wobei $P(v)=\{u|(u,v)\in E\}$ der Vorgänger von v ist und $S(v)=\{w|(v,w)\in E\}$ der Nachfolger von v ist.

Einschränkungen der Kapazität der Kanten werden eingehalten, auch bei negativem Fluss:

$|f_{q,z}(u,v)|\leq c((u,v))$

Außerdem ist der Fluss konsistent. Bei in beiden Richtungen nutzbaren Verbindungen wird als Nettoeffekt nur in eine Richtung gesendet und der entstehende negative Fluss nimmt den korrekten Wert an:

$f_{q,z}(u,v)=-f_{q,z}(v,u)$

Der Fluss wird für jeden Knoten $v\in V\backslash \{q,z\}$ mit Ausnahme der Quelle q und des Ziels z bewahrt:

$\sum _{u\in V}f_{q,z}(v,u)=0$

Der Wert eines Flusses beträgt:

$val(G,f_{q,z})=\sum _{u\in S(q)}f_{q,z}(q,u)$

Gesucht wird der maximale Fluss:

$max\{val(G,f)|$ f ist korrekter Fluss von q nach z}

Beispiel

Definiere $f_{1}$ durch

$f_{1}((1,2))=2,\ f_{1}((1,3))=4,\ f_{1}((2,4))=1,\ f_{1}((2,5))=1,\ f_{1}((3,2))=0,\ f_{1}((3,5))=4,\ f_{1}((4,5))=0,\ f_{1}((4,6))=1,\ f_{1}((5,6))=5$.

Daraus folgt, dass der Wert des Flusses 6 ist: $val(G,f_{1})=6$.

Definiere $f_{2}$ durch

$f_{2}((1,2))=5,\ f_{2}((1,3))=3,\ f_{2}((2,4))=4,\ f_{2}((2,5))=1,\ f_{2}((3,2))=2,\ f_{2}((3,5))=1,\ f_{2}((4,5))=1,\ f_{2}((4,6))=3,\ f_{2}((5,6))=3$.

Daraus folgt, dass $f_{2}$ kein Fluss ist.

Definiere $f_{3}$ durch

$f_{3}((1,2))=5,\ f_{3}((1,3))=9,\ f_{3}((2,4))=4,\ f_{3}((2,5))=5,\ f_{3}((3,2))=4,\ f_{3}((3,5))=5,\ f_{3}((4,5))=0,\ f_{3}((4,6))=4,\ f_{3}((5,6))=10$.

Daraus folgt, dass der Wert des Flusses 14 ist: $val(G,f_{3})=14$. Damit ist der Fluss $f_{3}$ maximal.