Maximaler Fluss, Ford Fulkerson: Unterschied zwischen den Versionen

Version vom 5. Februar 2008, 12:19 Uhr

Grundlegendes Konzept

Die Berechnung des kostenminimalen Maximalflusses im Graphen ist eine weitere wichtige Anwendungsform der Graphentheorie. Im Vergleich zum Dijkstra-Algorithmus, sowie des Floyd Algorithmus, wird hier die Betrachtung des optimalen (günstigsten, kürzesten, usw.) Weges um eine Kapazitätsbeschränkung der Wege erweitert: Über die verschiedenen Kanten eines Graphen kann nun jeweils nur maximal eine bestimmte Kapazitätsmenge geleitet werden. Das Ziel des Verfahrens besteht nun darin, den maximalen Fluss zu minimalen Kosten vom Ausgangs- zum Endknoten zu bestimmen. Dafür bestimmt man im ersten Schritt den günstigsten Weg von der Quelle zur Senke mit Hilfe des Dijkstra Algorithmus. Über diesen Weg leitet man die maximal mögliche Menge. Diese ergibt sich aus dem Minimum der Kapazitätsbeschränkungen der verwendeten Kanten. Anschließend führt man die wiederum maximal mögliche Menge über den zweitgünstigsten Weg von der Quelle zur Senke. Dieses Verfahren wird solange wiederholt bis kein Fluss mehr von Knoten Q zu Knoten S möglich ist. Die Gesamtkosten ergeben sich dann durch aufsummieren des jeweiligen Produktes von Menge * Kosten jeden Schrittes.

Mathematische Formulierung als LP-Modell

Kanten i,j
Kosten c_ij
Kapazität k_ij
Fluss f_ij

i=s Startknoten (Quelle)
j=z Zielknoten (Senke)

http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/FordFulkerson7.jpg

Erörterung am Beispiel

Der hier dargestellte Graph besteht aus den Knoten A, B, C und D. Der Knoten A stellt unsere Quelle dar und der Knoten D die Senke. Wir wollen nun möglichst viele Mengeneinheiten von A zu D liefern und dabei die Kosten so gering wie möglich halten. Dabei sind die Angaben an den Kanten des Graphen zu beachten (rote Zahlen). Die erste Zahl gibt die Kosten pro Mengeneinheit und die zweite die Kapazität der Kante an. Betrachten wir beispielsweise die Kante A-B, so stellen wir fest, dass der Fluss pro ME 20 GE kostet und maximal 5 ME von A nach B transportiert werden können. Im ersten Schritt berechnen wir nun mit Hilfe des Dijkstra Algorithmus den kostengünstigsten Weg von A nach D. Dabei ist zu beachten, dass an den Knoten jeweils der Vorgängerknoten V, die Kosten K, sowie die maximal mögliche Flusserhöhung F eingetragen werden. Es stellt sich heraus, dass der Weg A-C-B-D mit Kosten von 33 GE am günstigsten ist. Nun müssen wir die maximal mögliche Menge bestimmen, die über diesen Weg transportiert werden kann. Sie entspricht dem Minimum der Kapazitäten der durchlaufenen Kanten. In diesem Falle ist ein Transport von 2 ME möglich, da die Kante B-D nicht mehr Kapazität zur Verfügung stellt. Wir tragen an die Kanten nun nach jedem Schritt den kumulierten Fluss ein (wichtig: an Kanten, durch die nichts fließt, wird 0 eingetragen). Der Grund, weswegen wir an der Kante C-B die Flussrichtung eintragen, wird im 3. Schritt deutlich werden.

Im zweiten Schritt werden wir nun den nächst günstigsten Weg von Knoten A nach Knoten D suchen, dessen Kapazität noch nicht ausgelastet ist. Der Dijkstra-Algorithmus liefert uns als Ergebnis den Weg A-C-D, der mit Kosten von 35 GE veranschlagt wird. Es wird wiederum der größtmögliche Fluss über diese Strecke bestimmt, und an die Kanten eingetragen. Der Fluss wird durch die Kapazität der Strecke A-C begrenzt, die nur noch 6 ME liefern kann. Somit kann nach dem 2. Schritt festgehalten werden, dass die Strecke A-C, sowie B-D nicht mehr als Möglichkeit in Betracht kommen, da sie bereits komplett ausgelastet sind.

Der dritte Schritt, und somit der dritt günstigste Transportweg von A nach D, ergibt sich zu A-B-C-D. Allerdings bedarf die Kostenberechnung in diesem Falle einer ausführlicheren Erklärung: An den Richtungspfeilen der Kante C-B ist ersichtlich, dass ein Fluss von Knoten C zu Knoten B von 2 ME geplant ist, für den je 3 GE veranschlagt worden sind. Nun würden wir aber, bedingt durch das Ergebnis der dritten Durchführung des Dijkstra-Algorithmus, eine bestimmte Menge von Knoten B zu Knoten C transportieren wollen. Wenn man diese Menge nun auf 2 ME beschränkt, saldieren sich die Flüsse an der Kante. Dies wird deutlicher, wenn man es an einem praktischen Beispiel erklärt: Angenommen ein erster Fahrer transportiert 2 baugleiche Fahrräder von München nach Berlin, während gleichzeitig ein zweiter Fahrer 2 baugleiche Fahrräder von Berlin nach München transportiert. Dann ist mit gesundem Menschenverstand klar, dass man sich diese BEIDEN Transporte hätte sparen können. Zurück zu unserem Graphen: Zur Erinnerung sei erwähnt, dass wir im 1. Schritt die Kosten für den Transport von C nach B auf 5 GE pro ME beziffert haben (Wichtig: Flussrichtung mit Pfeilen markieren!). Da wir jetzt aber wissen, dass man sich diesen Transport sparen kann, und somit insgesamt keine Kosten anfallen dürfen, muss man im 3. Schritt für den Gegenfluss negative Kosten von 5 GE veranschlagen. Man hat damit einmal 2 ME mit je 5 GE = 10 GE ausgezeichnet, und den Gegenfluss von 2 ME mit je -5GE = -10 GE ausgezeichnet. Im Endeffekt sind somit also keine Kosten angefallen. Der dritte Weg (A-B-C-D) verursacht daher Kosten von 20-5+25 = 40 GE. Der maximale Fluss über diesen Weg ist durch die Kante B-C begrenzt, da die Kosten von 40 GE natürlich nur für die 2 ME Gültigkeit haben, die sich mit dem Gegenfluss saldieren lassen.

Im 4. Schritt bleibt uns wieder nur der Weg A-B-C-D, allerdings zu „normalen“ Kosten von 20+5+25 = 50 GE, mit einem Fluss von 2 ME (beschränkt durch Kante C-D). Nun wird deutlich, dass keine der Kanten die zur Senke führen, einen weiteren Fluss zulassen und damit ist die optimale Lösung gefunden.

Abschließend wollen wir die verschiedenen Wege inkl. der entstehenden Kosten nochmals in einer Tabelle darstellen:

MinCut - MaxFlow

Das MinCut – MaxFlow Theorem kann als Kontrollinstrument (gelbe Linie in Grafik) genutzt werden:

 Der maximale Fluss durch den Graphen (Max Flow) ist gleich der Kapazität
 der kapazitätsminimalen Schnittmenge (Min Cut).

Zusammenfassung

1. Ermittlung des jeweils kostenminimalen Weges von der Quelle „Q“ zur Senke „S“. Es werden nur solche Kanten berücksichtigt, deren Kapazität in die entsprechende Flussrichtung noch nicht voll ausgelastet ist (vgl. Dijkstra-Algorithmus).
2. An jedem Knoten werden der Vorgängerknoten „V“, die kumulierten Kosten „K“ je Flusseinheit und die maximal mögliche zusätzliche Flussmenge (im nächsten Iterationsschritt) „F“ eingetragen.
3. Kantenbeschriftung: Kosten und kumulierte Flussmenge (Kapazität).
4. Verteilung der maximalen Flussmenge auf die entsprechenden Knoten und Kanten.
5. Wiederholung ab Schritt 1 bis Senke S nicht mehr erreicht werden kann.

Vorlesung

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.

Vorlesungsmitschnitt zum Thema Ford Fulkerson vom 07.11.06 (Download)
Vorlesungsmitschnitt zum Thema Ford Fulkerson vom 14.11.06 (Download)

Achtung: die Dateien können fehlerhaft sein! Sobald dies möglich ist, werden aktuelle Mitschnitte aus dem WS 07/08 zur Verfügung gestellt.
Bitte beachten Sie die Hinweise zum Betrachten der Vorlesung.