R3 Flussprobleme
Ford-Fulkerson-Algorithmus anhand eines Beispiels
Der Ford-Fulkerson-Algorithmus wurde 1954 von den U.S.-Amerikanischen Mathematikern Lester Randolph Ford Junior und Delbert Ray Fulkerson erstmalig veröffentlicht.
Der Algorithmus strebt danach, in jeder Iteration den Fluss zu erhöhen. Über eine Subroutine werden dabei die Knoten untersucht, bis eine Flussvergrößernde Kette gefunden ist oder gezeigt ist, dass es keine solche gibt.
Der Algorithmus wird anhand des Beispiels in Abb. 3-14a eingeführt.
Die Kanten sind mit dem aktuellen Fluss xij und ihren Kapazitäten kij markiert. Zu Beginn sind die Flüsse auf allen Kanten 0 und der Fluss durch das Netzwerk f ebenfalls. Im Verlauf des Algorithmus werden die Knoten mit einer Markierung s(+/-);
gekennzeichnet. Zu Beginn ist nur die Quelle mit - ,∞ markiert. Das bedeutet, dass an der Quelle ein beliebig hoher Fluss zur Verfügung steht.
Iteration 1
1. Subroutine Knoten A bearbeiten
Als Ausgangspunkt für die Flussvergrößerung dient die Quelle, sie wird als Arbeitsknoten gewählt. Über die Kante (A;B) ist es möglich, einen Fluss von maximal 4 Einheiten zum Knoten B fließen zu lassen. Deswegen wird der Knoten B mit A+; 4 markiert. Der erste Teil der Markierung erlaubt zurückzuverfolgen, welches der letzte Knoten ist und das + zeigt an, dass es sich um eine Flussvergrößerung handelt. Die 4 wiederum gibt die bis zu diesem Knoten mögliche Flussvergrößerung an.
Von A geht noch der Pfeil (A;C) aus, entsprechend wird der Knoten C mit A+;7 markiert. Die Quelle A wird als abgearbeitet markiert.
2. Subroutine Knoten B bearbeiten
Als nächstes wird ein markierter aber nicht endgültig abgearbeiteter Knoten als Arbeitsknoten gewählt. Zur Auswahl stehen B und C, im Beispiel wird B gewählt.
Nun müssen alle Kanten die am Arbeitsknoten beginnen oder enden betrachtet werden. Wenn der Knoten am anderen Ende der Kante noch nicht markiert ist, ist ein genauerer Blick auf die Kante notwendig. Ist es möglich bei einer vom Arbeitsknoten ausgehenden Kante den Fluss zu erhöhen oder bei einer eingehenden den Fluss zu verringern? Wenn ja, dann wird der benachbarte Knoten markiert.
Die Kante (B;D) führt zu einem noch nicht markierten Knoten und lässt einen Fluss von 5 zu. Wie die Markierung von B aber zeigt, kann der Fluss von der Quelle zu B um maximal 4 Einheiten erhöht werden. Der kleinere Wert ist maßgeblich:
Deshalb wird D mit B+;4 markiert.
Nach dem gleichen Vorgehen wird nun noch am Knoten E die Markierung E+;3 angebracht.
Damit ist B abgearbeitet und wird endgültig markiert.
3. Subroutine Knoten D bearbeiten
Und wieder kann ein markierter aber noch nicht abgearbeiteter Knoten gewählt werden, zu Auswahl stehen D und C. Im Beispiel wird D gewählt.
In den Knoten D führt die Kante (C;D), auf der findet noch kein Fluss statt, zudem trägt C selbst schon eine Markierung, von daher ist hier keine Aktion erforderlich.
Von D aus lässt sich aber Z markieren. Ein Durchbruch (engl. breakthrough) zur Senke ist geschlagen! Die Senke wird mit D+;4 gekennzeichnet. Es brauchen in dieser Iteration keine weiteren Knoten bearbeitet werden.
Fluss erhöhen und Markierungen löschen
Über die Markierungen lässt sich nun die Flussvergrößernde Kette zurückverfolgen. Auf Kanten auf die über eine Markierung mit einem „+“ verwiesen wird, wird er um 4 Einheiten vergrößert. Auf Kanten mit einem „-“ würde er verkleinert, aber das ist in dieser Iteration noch nicht der Fall.
Abschließend werden alle Markierungen einschließlich der endgültigen Markierungen für abgearbeitete Knoten gelöscht.
Iteration 2
1. Subroutine Knoten A bearbeiten
Wieder wird mit der Quelle gestartet. Über die Kante (A;D) ist keine weitere Flussvergrößerung möglich, deshalb kann von A aus der Knoten B nicht markiert werden.
Der Knoten C lässt sich aber mit A+, 7 markieren.
2. Subroutine Knoten C bearbeiten.
Von C aus werden in bekannter Weise D mit C+;4 und E mit C+;1 markiert.
3. Subroutine Knoten D bearbeiten.
In den Knoten D führt eine Kante von B kommend hinein. B ist noch nicht markiert und auf der Kante findet ein Fluss von 4 Einheiten statt. Es wäre möglich den Fluss zu senken, von daher erhält B die Markierung B-,4.
Die Kante von D nach Z hat eine Kapazität von 6 Einheiten, es findet bereits ein Fluss von 4 statt, d.h. es sind 2 zusätzliche Einheiten möglich. Der Rechenweg zu dieser Überlegung lautet:
Es ist ein Durchbruch gefunden.
Fluss erhöhen und Markierungen löschen
Der Fluss durch das Netzwerk kann um 2 Einheiten erhöht werden, der Pfad lässt sich über die Markierungen zurückverfolgen. Der Fluss im Netzwerk beträgt damit 4+2=6 Einheiten. Wieder sind sämtliche Markierungen einschließlich der Markierungen für abgearbeitete Knoten zu löschen.
Iteration 3
1. Subroutine Knoten A bearbeiten
Über die Kante (A;C) ist eine weitere Flusserhöhung von 5 möglich.
2. Subroutine Knoten C bearbeiten
Von Knoten C aus können D mit C+;2 und E mit C+;1 markiert werden.
3. Subroutine Knoten D bearbeiten
Der Fluss zu dem noch nicht markierten Knoten B lässt sich um 4 absenken, da aber im Knoten D nur 2 Einheiten bereitgestellt werden können ist die Markierung 2. Formal ausgedrückt:
Über die Kante (D; Z) ist kein weiterer Fluss möglich, Z kann deshalb nicht vom Knoten D aus markiert werden.
4. Subroutine Knoten E bearbeiten
Vom Knoten E aus ist es möglich den Knoten Z zu markieren und einen Durchbruch zu schaffen. Es ist insgesamt eine weitere Einheit möglich.
5. Fluss erhöhen und Markierungen löschen
Der diesmal um eine Einheit erhöhte Fluss ist einzutragen. Die Markierungen sind zu löschen. Der Fluss insgesamt beträgt nun 7.
Iteration 4
1. Subroutine Knoten A bearbeiten
Wie bekannt, es sind noch 4 Einheiten möglich
2. Subroutine Knoten C bearbeiten
Über die Kante (C;D) sind zwei weitere Einheiten möglich.
Die Kante (C;E) ist bereits an ihrer Kapazitätsgrenze, es ist keine Markierung möglich.
3. Subroutine Knoten D bearbeiten
Es führt eine Kante von B nach D, auf der ein Fluss von 4 stattfindet, B ist noch nicht markiert.
Deswegen ist B wie auch in der vorherigen Iteration mit D-;2 zu markieren.
4. Subroutine Knoten B bearbeiten
Es führt eine Kante von A nach B, A ist bereits markiert, von daher ist keine Aktion erforderlich. Über die Kante von B nach E sind noch 3 Einheiten möglich, im Knoten B können 2 Einheiten bereitgestellt oder, besser gesagt, umgelenkt werden. Von daher wird E mit B+;2 markiert.
5. Subroutine Knoten E bearbeiten
Die Kante (C;E) ist nicht zu betrachten, da C bereits markiert ist.
Über die Kante (E;Z) ist eine Flussvergrößerung von 4 möglich, 2 Einheiten können in E bereitgestellt werden. Deshalb kann Z mit E+;2 markiert werden und ein Durchbruch ist geschaffen.
6. Flüsse ändern und Markierungen löschen
Auf den in Pfeilrichtung genutzten Kanten ist der Fluss nun um 2 Einheiten zu erhöhen, auf den entgegen Pfeilrichtung genutzten zu senken.
Über den Weg A-C-D-Z wird der Fluss um 2 Einheiten erhöht. Ein Teil des in Iteration 1 konstruierten Flusses A-B-D-Z wird über die Kanten A-B-E-Z umgeleitet. Der Fluss über die Kante D-Z bleibt konstant, der Zufluss in den Knoten D von B wird um 2 Einheiten gesenkt, dafür wird der Zufluss von C in gleichen Maßen erhöht.
Iteration 5
1. Subroutine Knoten A bearbeiten
Wie bekannt, es sind noch 2 Einheiten möglich.
2. Subroutine Knoten B bearbeiten
Die Kante (C;D) ist an der Kapazitätsgrenze, es ist keine Markierung von D möglich, das Gleiche gilt für die Kante (C;E).
Es gibt keine weiteren markierten Knoten, die noch nicht abgearbeitet sind. Es kann kein Durchbruch gefunden werden (engl. non breakthrough), der Fluss lässt sich nicht vergrößern. In der vorherigen Iteration wurde bereits der maximale Fluss gefunden.
Ergebnis
Die markierten Knoten sind A und C, alle anderen sind nicht markiert.
Die Schnittkanten T sind
Der Maximale Fluss beträgt 9 Einheiten, der Wert lässt sich durch Summieren der Flussvergrößerungen in den einzelnen Iterationen ermitteln oder alternativ durch Summieren der Kapazität der Vorwärtskanten über den Schnitt.
Wenn die Berechnungen korrekt sind, muss auf allen Vorwärtskanten über den Schnitt xij=kij gelten. Auf Rückwärtskanten (im Beispiel nicht vorhanden) darf kein Fluss sein, d.h. es muss xij=0 gelten.
Bemerkungen
Natürliche Ganzzahligkeit
p> Wenn die Kapazitätsgrenzen ganzzahlig sind und auch ein eventuell anfänglich vorhandener Fluss ganzzahlig ist, treten während Lösung und als Ergebnis nur ganze Zahlen auf. Man spricht von natürlicher Ganzzahligkeit.Bei vielen anderen Problemen ist inhaltlich nur eine ganzzahlige Lösung zulässig und im Laufe der Berechnung müssen die Ergebnisse mit großem Aufwand ganzzahlig gemacht werden, bei Flussproblemen funktioniert es von alleine.
Wahl der Arbeitsknoten
Bezüglich der Wahl der Arbeitsknoten bestehen, wie sich im Beispiel gezeigt hat, oftmals Wahlmöglichkeiten. Es bleibt jedem Anwender überlassen, hier eine Auswahlregel zu finden, die besonders effizient ist.
