A maximum flow Der Algorithmus von Ford und Fulkerson Technische Universität München
Suche


Flussnetzwerk \(N = (G, c, s, t)\) mit maximalem Fluss der Stärke f * \( = 6\)


Das Max-Flow Problem

-Die Suche nach maximalen Füssen

Die Suche nach maximalen Flüssen in der Graphentheorie wird von ihrer Praxisrelevanz besonders motiviert. Denn in eine typische Anwendung von Graphen ist, sie zur Modellierung von Transportnetzwerken wie beispielsweise Pipelines, Stromtrassen oder Datennetzwerken zu verwenden.

In solchen Anwendungen geht es hauptsächlich um den Transport beliebiger Ressourcen -formal als Fluss definiert- von einer bestimmten Quelle zu einem bestimmten Ziel. Dabei hat man oft auf dem Weg zum Ziel gewisse Einschränkungen in Form von oberen Schranken für die Anzahl an zu transportierenden Ressourcen, die als Kantenkapazitäten bezeichnet werden.

Das Ziel von einem Max-Flow Problem ist die Findung eines maximalen Flusses unter Einhaltung der gegebenen Kapazitäten.


Dieses Applet stellt den Algorithmus von Ford und Fulkerson vor, welcher in einem gegebenen Netzwerk den maximalen Fluss von einer Quelle zu einer Senke berechnet.

Was möchtest du zuerst tun?


Legende

node Knoten
edge Kante mit Kapazität 10

Legende

Auf welchem Graph soll der Algorithmus ausgeführt werden?

Nimm ein fertiges Beispiel!

Ändere den Graphen nach deinen Vorstellungen:

  • Um einen Knoten zu erstellen, mache einen Doppelklick in das Zeichenfeld.
  • Um eine Kante zu erstellen, klicke zunächst auf den Ausgangsknoten und dann auf den Zielknoten.
  • Das Kantengewicht kann mit einem Doppelklick auf die Kante verändert werden. Negative Gewichte nicht erlaubt!
  • Ein Rechtsklick löscht Kanten und Knoten.

Anmerkung: Wir erlauben hier keine Paare entgegengesetzter Kanten. Siehe die Beschreibung des Algorithmus für die Erklärung!

Lade den veränderten Graphen herunter:

Download

Lade einen existierenden Graphen hoch:

Ein

trat auf beim Lesen der Datei:

Fehlerbeschreibung:

                    

Was nun?

Legende

node Knoten
node S/T Knoten
edge Kante mit Kapazität 10 und Fluss 7.
edge Kante im Residualgraphen.
edge Kante auf augmentierendem Pfad.

Legende

Status des Algorithmus

Wähle zuerst eine Quelle!

Klicke auf einen Knoten, um ihn als Quelle \(s\) auszuwählen.

Intuitiv ist diese Quelle der Startknoten, von dem der Fluss ausgeht.

Wähle nun eine Senke!

Klicke auf einen Knoten, um ihn als Senke \(t\) auszuwählen.

Intuitiv ist die Senke dann der Zielknoten, zu dem der Fluss fließt.

Algorithmus von Ford und Fulkerson

Gegeben ist nun der erstellte Graph \(G = (V,E)\) mit den jeweiligen nicht-negativen Kantenkapazitäten \(c(e)\) für alle Kanten \(e \in E\), sowie die gewählten Quelle \(s\) und Senke \(t\).

Zusammen bilden diese ein Flussnetzwerk \(N = (G,c,s,t)\).

Ziel dieses Algorithmus ist ausgehend vom Flussnetzwerk \(N\) Flusswerte \(f(e)\) für alle Kanten \(e \in E\) unter Einhaltung der Kapazitätsgrenzen \(c\) zu bestimmen, sodass der Gesamtfluss f * maximal ist.

Dabei ist f * der Fluss, der von der Quelle \(s\) zur Senke \(t\) fließt, d.h. die Summe der Flusswerte aller Kanten, die \(s\) verlassen, was zugleich die Summe der Flusswerte aller Kanten, die in \(t\) ankommen, ist.


Klicke nun auf Nächster Schritt, um den Algorithmus zu starten!

Initialisiere den Fluss!

Nehme den sogenannten Nullfluss als Startfluss, d.h. setze \(f(e) = 0\) für alle Kanten \(e \in E\) des Graphen \(G\).

Im Laufe des Algorithmus wird dieser Startfluss erhöht, bis der maximaler Wert erreicht wird.



Anmerkung: Der Algorithmus kann an sich mit einem beliebigen Fluss gestartet werden, solange die Kapazitäten eingehalten werden. Der Nullfluss ist allerdings eine gute Wahl für den Startfluss, da er ohne weitere Überprüfung die nicht-negativen Kapazitätsgrenzen garantiert respektiert.

Beginne die Hauptschleife!

Die Hauptschleife wird solange durchlaufen, bis kein Pfad von \(s\) nach \(t\) im Augmentationsnetzwerk \(N_f\) gefunden wird.

Ein solcher Pfad in \(N_f\) wird augmentierenden Pfad genannt. Entlang dieses Pfades wird der Gesamtfluss vergrößert.

Das Augmentationsnetzwerk, das nun im nächsten Schritt konstruirt wird, gibt für alle Kanten Informationen darüber, um wie viel der Fluss in der jeweilige Kante vergrößert bzw. verringert (durch die Einführung von Hin- bzw. Rückkanten) werden kann.


Klicke nun auf Nächster Schritt, um mehr über die Konstruktion von \(N_f\) zu erfahren.


Möchtest du selbst üben?

Erhöhe entlang des augmentierenden Pfades!

Nachdem im letzten Schritt den Augmentationswert \(a\) bestimmt wurde, wird nun der Gesamtfluss f * um \(a\) vergrößert.

Anschließend wird der Pfad augmentiert, d.h setze

\(f(e) = f(e) + a\), falls die Hinkante \(e'\) von e ist im Pfad enthalten und

\(f(e) = f(e) - a\), falls die Rückkante \(e''\) von e ist im Pfad enthalten.


Wie wird aber ein augmentierender Pfad überhaupt gefunden?

Fertig

Kein (\(s,t\))-Pfad im Augmentationsnetzwerk mehr gefunden.

Der Algorithmus bricht mit folgendem Wert als maximalen Fluss f * ab:


Anmerkung: Der Algorithmus von Ford und Fulkerson gibt immer einen maximalen Fluss aus, falls er terminiert. Sind alle Kapazitäten nichtnegative ganze Zahlen, so terminiert der Algorithmus garantiert nach endlich vielen Schritten.

Möchtest du weitere Details über den Algorithmus erfahren?

s ← wähle(v)

t ← wähle(v)

BEGIN

INPUT: Flussnetzwerk N = (G,c,s,t)

mit G = (V,E), s,t ∈ V

OUTPUT:Flusswerte f(e) für alle e ∈ E,

maximaler Fluss f*

(* Initialisere den Fluss *)

FOR { e ∈ E } DO

f(e) ← 0

(* Hauptschleife *)

WHILE ex. (s,t)-Pfad im Aug.netzwerk DO

f* ← f* + Anpassung

FOR {e ∈ Pfad}

f(e) ← f(e) + Anpassung

RETURN f, f*

END

Variablen

Pfad Anpassung
{} 0

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.

SVG Download

Legende

node Knoten
node S/T Knoten
edge Kante mit Kapazität 10 und Fluss 7.
edge Kante im Residualgraphen.
edge Kante auf augmentierendem Pfad.

Legende

Prüfe dein Wissen: beantworte die Fragen!

Ist der Fluss bereits maximal?

Was ist der augmentierender Wert?

Welche Kapazitäten haben die Kanten im Augmentationsnetzwerk?

-Hier hast du die Möglichkeit, solche Fragen zu beantworten und den Algorithmus nochmal auszuführen!


Wähle einen Graphen für diese Aufgabe aus!

Klicke nun auf nächster Schritt um die Aufgabe zu beginnen!

Wähle zuerst eine Quelle!

Klicke auf einen Knoten, um ihn als Quelle s auszuwählen.

Wähle nun eine Senke!

Klicke auf einen Knoten, um ihn als Senke t auszuwählen.

Algorithmus von Ford und Fulkerson

Ausgehend von dem gegebenen Flussnetzwerk N = ( G , c , s , t ) sucht der Algorithmus Flusswerte f ( e ) für alle Kanten e unter Einhaltung der Kapazitätsgrenzen c , sodass der Gesamtfluss f * maximal ist.


Im Laufe der Ausführung werden dir Multiple-Choice-Fragen gestellt!

Klicke nun auf Nächster Schritt, um den Algorithmus zu starten!

Initialisiere den Fluss!

Nehme den sogenannten Nullfluss als Startfluss, d.h. setze f ( e ) = 0 für alle Kanten e des Graphen G .

Im Laufe des Algorithmus wird dieser Startfluss erhöht, bis der maximaler Wert erreicht wird.

Beginne die Hauptschleife!

Die Hauptschleife wird solange durchlaufen, bis kein augmentierender Pfad von s nach t im Augmentationsnetzwerk N f gefunden wird.

Erhöhe entlang des augmentierenden Pfades!

Der Pfad augmentiert, d.h der aktuelle Fluss f ( e ) aller Kanten e des Pfades werden um diesen Wert a erhöht.

Der Gesamtfluss f * wird um den Augmentationswert a vergrößert.

Fertig

Kein ( s , t ) -Pfad im Augmentationsnetzwerk mehr gefunden.

Der Algorithmus bricht mit folgendem Wert als maximalen Fluss f * ab:

Möchtest du weiter üben?

s ← wähle(v)

t ← wähle(v)

BEGIN

INPUT: Flussnetzwerk N = (G,c,s,t)

OUTPUT:Flusswerte f(e) für alle e ∈ E,

optimaler Fluss f*

(* Initialisere den Fluss *)

FOR { e ∈ E } DO

f(e) ← 0

(* Hauptschleife *)

WHILE ex. (s,t)-Pfad im Aug.netzwerk DO

f* ← f* + Anpassung

FOR {e ∈ Pfad}

f(e) ← f(e) + Anpassung

RETURN f, f*

END

In diesem Teil kannst du dein Wissen testen

Der Algorithmus wird normal ausgeführt, stoppt aber an einigen Stellen, an denen Fragen gestellt werden.

Tipp: Vorher nochmals die Beschreibung des Algorithmus durchlesen.

Viel Erfolg!

Beim Wechsel des Tabs wird die Aufgabe abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.

SVG Download

Legende

node Knoten
node S/T Knoten
edge Kante mit Kapazität 10 und Fluss 7.
edge Kante im Residualgraphen.
edge Kante auf augmentierendem Pfad.

Legende

Bilde das entsprechende Augmentationsnetzwerk!

Gebe die Kapazitäten im Augmentationsnetzwerk an!

Im Folgenden kriegst du verschiedene Netwerke \(N\) mit jeweiligen Kapazitäts- und Flusswerte \(c(e)\) und \(f(e)\) für alle Kanten \(e \in E\), basierend auf einem aktuellen Fluss \(f\).

Deine Aufgabe ist die fehlenden Kapazitäten \(c(e')\) bzw. \(c(e'')\) der Hin- bzw. Rückkanten \(e'\) und \(e''\) im entsprechenden Augmentationsnetzwerk N f einzutragen.


Wähle eine Anzahl an Netzwerke für diese Übung:


In diesem Teil kannst du die Konstruktion von Augmentationsnetzwerken üben!

Du kriegst ein Netzwerk mit einem aktuellen Fluss gegeben. Gebe die fehlenden Kapazitätswerten für das Augmentationsnetzwerk an!

ACHTUNG: Du darfst die Kapazitäten jeweils nur einmal angeben!

Tipp: Vorher nochmals die Informationen zu Augmentationsnetzwerken durchlesen.

Viel Erfolg!

Beim Wechsel des Tabs wird die Aufgabe abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.