Maximaler Fluss, Ford Fulkerson

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

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 1: Graph vor der Berechnung

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 2: Graph nach 1. Schritt

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 3: Graph nach 2. Schritt

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 4: Graph nach 3. Schritt

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 5: Graph nach 4 Schritt - Lösung.

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

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 6: Übersicht der Wege und Kosten

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.

Fundamental concept

The calculation of a graph's maximal flow at minimal costs is another important application area of graph theory. In contrast to Dijkstra and Floyd-Algorithm the analysis of the optimal solution (cheapest, shortest, etc.) is expanded with an additional factor namely capacity limits: Only a predetermined maximal amount of capacity can pass an edge. The technique aims to find out the maximal flow from an initial node to end node with minimal costs. Therefore the most cost-minimal path from source to sink is to be identified by Dijkstra-Algorithm. Along this path the maximal possible amount of capacity is sent. This amount is determined by the minimum capacity limit of all passed edges. Afterwards the maximal possible amount from source to sink is sent through the second best solution of Dijkstra-Algorithm. This procedure is repeated until no longer flow is possible from node q to node s. The summation of each amount multiplied by the costs of the concerned step deliver the total costs.

Linear program formulation

edges i,j
costs c_ij
capacity k_ij
flow f_ij

i=s initial node (source)
j=z goal node (sink)

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

Example

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 1: Graph vor der Berechnung

The graph presented above is composed of the nodes A,B,C and D. Node A represents our source while node D stands for the sink. The aim is to send as much quantity units as possible at the least possible costs. Therefore attention has to be paid to the numbers at the edges (red numbers). The first number indicates the costs per unit and the second one the capacity of the edge. Considering for example edge A-B we can see that the flow of one quantity unit costs 20 MU and beside only a total 5QU can be transported through this edge. In the first step the cost-minimal path from A to D is to be detected by Dijkstra-Algorithm. In this context it is important to note at each vertex the predecessor node, the costs as well as the maximal possible increase of the flow. Dijkstra-Algorithm delivers the solution A-C-B-D with the costs of 33 MU per unit. Now we have to find out the maximal amount that we can send through this path. This amount is in accordance with the minimum of the capacities of all passed edges. In this case only a flow of 2 QU is possible since edge B-D allows no more capacity. At each stage the accumulated flow is registered at the edges (important:in case of no flow write 0).The reason why we record the flow direction of edge C-B will be explained in the third step.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 2: Graph nach 1. Schritt

In the second step we search the next best path from A to D whose capacity is not fully exploited. Dijkstra-Algorithm delivers path A-C-D with costs of 35 ME per unit. Again the maximal possible flow is to find out and note at the edges. This flow is restricted by the capacity of edge A-C which only allows a total transport of 6 quantity units. After the second step we can cross out the routes A-C as well as B-D since their capacity is fully utilized and no more flow is possible.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 3: Graph nach 2. Schritt

The third step and thus the calculation of the third best path from A to D delivers path A-B-C-D. However cost calculation in this step is trickier than previous steps: The directional arrow at edge C-B shows that a flow of 2 QU with costs of 3 MU per unit from C to D is planned. Since the third best path is A-B-C-D we are going to send flow from B to C. Restricting this flow to 2 quantity units the flows at this edge balance. Explaining this incident by an practical example will provide greater clarity: We suppose the first driver transports 2 identical bikes from Munich to Berlin, while the second driver also transports 2 identical bikes from Berlin to Munich. Apparently this transport is nonsensical and can be deleted completely. Transferred to our network of nodes: In the first step we send flow from C to B with costs per unit of 5 MU (important: notation of the flow direction!). However in the third step it becomes clear that we can delete this transport. Consequently no costs arises at this edge. This means that the costs we registered in the first step have to be equalized. By estimating negative costs of 5 MU per unit in the third step we can even out the total costs of this edge. Consequently we have primarily a flow with 5MU+5MU = 10MU and afterwards an inverted flow of -5MU + -5MU= -10MU, which means an equalization of the costs thus no costs. According to this path A-B-C-D causes total costs in the amount of 25-5+25=40 MU. In this case the maximal flow is restricted to 2 quantity units since the balancing of the transports in edge B-C is only accomplishable for 2 quantity units.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 4: Graph nach 3. Schritt

In the fourth step path A-B-C-D is utilized again. The only difference to the third step is that we have 'oridinary' costs of 20+5+25=50 MU now. The flow is restricted through edge C-D to an amount of 2 quantity units. Now it becomes clear that no edge permits any flow from source to sink. The optimal solution is identified.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 5: Graph nach 4 Schritt - Lösung.

Concludingly we summarize all different paths as well as their costs in the following table:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 6: Übersicht der Wege und Kosten

Min Cut - Max Flow

The MinCut – MaxFlow theorem may be used as a control tool (yellow line in the network):

 The maximum value of a flow through a graph (Max Flow) is equal to the
 to the capacity sum of the cut with minimal capacity (Min Cut).

Step-by-step Summary

1. Detection of the path at the least possible costs from source 'Q' to sink 'S'. In this context only edges whose capacities are not fully exploited in the concerned flow direction are considered in the analysis (cf. Dijkstra-Algorithm).
2. At each edge the values of predecessor nodes 'V' as well as accumulated costs 'K' and additional maximal possible flow quantity (next iteration)'F' are noted.
3. Labels of the edges: costs and accumulated quantities of flow (capacity)
4. Allocation of the maximum flow amount on relevant edges and vertices
5. Iteration starting with step 1 until it is no more possible to achieve sink S