Der maximale s-t Fluss hat den Wert 6

Das Max-Flow Problem

Eine typische Anwendung von Graphen ist, sie zur Modellierung von Transportnetzwerken wie beispielsweise Pipelines, Stromtrassen oder Datennetzwerken zu verwenden. Häufig ist es dabei nötig, die Kanten der Netzwerke mit Kapazitäten auszustatten, welche die maximale Menge der darüber transportierbaren Ressource angeben.

Eine interessante Eigenschaft von diesen Netzwerken ist nun die maximale Menge der von einem Punkt zu einem anderen Punkt transportierbaren Ressource. Dies wird das Max-Flow Problem genannt.

Dieses Applet stellt den Algorithmus von Ford und Fulkerson vor, welcher in einem gegebenen Netzwerk den maximalen s-t Fluss berechnet.

Maximale Flüsse

Mit Hilfe von Graphen kann man mathematische Modelle für verschiedene Anwendungen erstellen. Ein naheliegender Problemtyp behandelt Netzwerke, welche eine Ressource von einem Punkt zu einem anderen transportieren - beispielsweise Wasser, Waren, oder Daten.

Allgemein wird diese Problemklasse die Klasse der Flussprobleme genannt.. Ein Flussproblem ist definiert durch den die Netzwerkstruktur abbildenden Graphen, welcher häufig noch weitere Informationen enthält. So wird häufig für jede Kante des Graphen die maximale Menge der darüber transportierbaren Ressource angegeben - ihre Kapazität c(e). Weiterhin benötigt man eine Quelle und eine Senke des Flusses.

Eine Lösung eines Flussproblem ist eine Zuordnung, welche jeder Kante die darüber fließende Menge der Ressource zuweißt. Ein zulässiger Fluss muss hierbei zwei Bedingungen erfüllen: Jede Kante kann maximal die Menge ihrer Kapazität transportieren. Weiterhin muss für jeden Knoten des Graphen (ausgenommen Quelle und Senke) die Summe der eingehenden Flüsse gleich der Summe der ausgehenden Flüsse sein.

Das grundlegendste Flussproblem ist die Berechnung eines maximalen Flusses: Wie viele Ressourcen können maximal von einem Quellknoten zur Senke transportiert werden.

Idee des Algorithmus

Der Algorithmus von Ford und Fulkerson berechnet einen maximalen Fluss auf iterativem Weg, indem er mit einem zulässigen Fluss startet und diesen dann schrittweise so anpasst, dass die Anforderungen an einen Fluss immer noch erfüllt sind und gleichzeitig die Größe des Flusses erhöht wird.

Ein wichtiges Konzept des Algorithmus ist der Residualgraph eines Fluss. Dieser Graph wird erzeugt, indem berechnet wird wie der Fluss entlang einer Kante verändert werden kann - so wird jede Kante des ursprünglichen Netzwerks im Residualgraph durch maximal zwei Kanten ersetzt. Eine Kante in gleicher Richtung gibt an, wie viel der Fluss noch erhöht werden kann, und eine Kante in Gegenrichtung gibt an, wie viel der Fluss noch reduziert werden kann.

Der Algorithmus beginnt mit einem leerer Fluss (welcher immer zulässig ist) und sucht dann wiederholt im Residualgraphen nach Pfaden von Quelle zu Senke. Indem der Fluss entlang des gefundenen Pfades so weit erhöht wird, bis die Kapazität der ersten Kante erreicht ist (d.h. sie saturiert ist), bleibt der Fluss zulässig und wird zugleich größer. Diese Pfade werden augmentierende Pfade genannt.

Wie findet man Pfade im Residualgraph?

Der Algorithmus von Ford und Fulkerson definiert nicht explizit, wie die augmentierenden Pfade gesucht werden sollen, und arbeiten mit jedem beliebigen Suchalgorithmus für Pfade. Die genaue Wahl des Suchalgorithmus hat jedoch einen Einfluss auf die (worst case) Laufzeit des Algorithmus. Tiefensuche ist eine vergleichsweise schlechte Wahl, Breitensuche gibt bessere Ergebnisse. Diese Variante mit Breitensuche wird auch Edmonds-Karp Algorithmus genannt. Eine weitere Variante mit noch besserer Laufzeit ist der Algorithmus von Dinic.

Was nun?

Wie sieht der (Pseudo-)Code des Algorithmus aus?

Input: Graph G=(V,E), Kostenfunktion c'(e)
Output: Fluss f(e)

s ← wähle(v)
t ← wähle(v)
BEGIN
(* Initialisiere Fluss *)
FOR { e  ∈ E } DO
  f(e) ← 0
(* Hauptschleife *)
WHILE augm. Pfad könnte existieren DO
  Pfad ← FINDE_PFAD_IN_RESIDUALGRAPH()
  IF Pfad EXISTS;
    Anpassung ← min(c'(e) | e ∈ Pfad);
    FOR {e ∈ Pfad}
      f(e) ← f(e) + Anpassung
END

Wie schnell ist der Algorithmus?

Literatur

Wo finde ich noch mehr Informationen zu Graphalgorithmen?

Ein letzter Hinweis zum Ziel und Inhalt dieser Seite und zu Zitationen