Flussnetzwerke und Maximale Flüsse

Flussnetzwerke spielen in der Informatik eine sehr wichtige Rolle, da sie Modell für viele praktische Probleme sind.

Ein Netzwerk ist ein gerichteter Graph mit einer Kapazitätsfunktion auf den Kanten sowie zwei speziellen Knoten $s$ und $t$. Man schreibt auch Kurz $D = (V,E,s,t,c)$, wobei $(V,E)$ der gerichtete Graph mit Knoten $V$ und Kanten $E$ ist, und $c: E \to \mathbb{N}$ die Kapazitätsfunktion. Man kann sich die Kanten zwischen den Knoten als "Rohrleitungen" vorstellen und die Kapazität einer Kante ist ein Maß dafür wie dick das Rohr ist, bzw. wie viel Wasser hindurchfließen kann.

Das Optimierungsproblem besteht nun darin einen maximalen Fluss von der Quelle $s$ (Source) zur Senke $t$ (Target) fließen zu lassen.

Dabei definieren wir einen Fluss $f$ auf dem Netzwerk als eine Abbildung $f: E \to \mathbb{N}$ die für jede Kante anzeigt wieviel durch sie hindurch fließt. Dabei müssen die folgenden Bedingungen an $f$ gestellt werden, damit $f$ einen gültige Fluss modelliert:

  1. Kapazitätsbedingung: "Es kann nie mehr durch eine Kante hindurchfließen als die Kapazität erlaubt":

    \begin{gather*} \forall e \in E: f(e) \leq c(e) \end{gather*}

  2. Flusserhaltungsbedingung: "Für jeden Knoten im Netzwerk - außer $s$ und $t$ - muss genausoviel hinausfließen wie auch hineinfließt":

    \begin{gather*} \forall v \in V \setminus \{s,t\}: \sum_{(v,i) \in E} f((v,i)) = \sum_{(i,v) \in E} f((i,v)) \end{gather*}

Der Wert des Flusses $f$ ist nun das was von $s$ nach $t$ insgesamt fließt, also das was aus $s$ tatsächlich heraussprudelt:

\begin{gather*} w(f) := \sum_{(s,i) \in E} f((s,i)) - \sum_{(i,s) \in E} f((i,s)) \end{gather*}

Diesen Wert wollen wir maximieren.

Es gibt nun zwei sehr schöne Algorithmen die zu einem gegebenen Netzwerk einen maximalen Fluss berechnen. Das unten stehende Applet visualisiert die beiden Algorithmen. Zunächst möchte ich sie aber kurz erklären.

Algorithmus von Ford & Fulkerson

Der Algorithmus von Ford & Fulkerson sollte jedem Informatiker schonmal über den Weg gelaufen sein daher möchte ich garnicht so viel dazu sagen. Er ist sehr einfach, denn er sucht sich sukzessive "erhöhende Wege" von der Quelle zur Senke, und erhöht dann den Fluss entlang des Weges um den maximal möglichen Betrag. Existiert kein erhöhender Weg mehr, so terminiert der Algorithmus und der berechnete Fluss ist maximal.

Ein erhöhender Weg ist ein semi-Weg von $s$ nach $t$, er kann also insbesondere auch Rückwärtskanten enthalten. Der Weg ist jedoch nur ein gültiger erhöhender Weg, falls für jede Vorwärtskante auf dem Weg die Kapazität bezüglich des aktuellen Flusses nicht erschöpft ist, und für jede Rückwärtskante ein Fluss echt größer $0$ fließt. Das Finden eines solchen erhöhenden Weges ist zum Beispiel über Breitensuche (BFS) möglich.

Algorithmus von Goldberg & Tarjan (Push & Relabel Algorithmus)

Dieser Algorithmus verfolgt einen komplett anderen Ansatz. Wir erlauben während der Durchführung des Algorithmus "Präflüsse", das sind Flüsse die die oben genannt Flusserhaltungsbedingung derart verletzen, dass in einen Knoten mehr hineinfließen kann als hinausfließt. Die Differenz heißt Flussüberschuss und gilt jeweils für einen Knoten.

Der Algorithmus besteht nun aus zwei Kernoperationen: PUSH und RELABEL. Die PUSH Operation versucht Flussüberschuss aus einem Knoten an Nachbarknoten weiterzuschieben. Dies ist jedoch nur erlaubt, wenn die Nachbarknoten eine geringere Höhe haben. Ein Knoten kann sich durch eine RELABEL Operation erhöhen. Dies ist jedoch nicht beliebig möglich, sondern die neue Höhe entspricht der minimalen Höhe aller Nachbarknoten zu denen noch etwas geschoben werden kann, plus eins. Insgesamt funktioniert der Goldberg & Tarjan Algorithmus wie folgt: Die Quelle wird zunächst auf Höhe $|V|$ angehoben, und es wird so viel Fluss wie möglich aus der Quelle in die Nachbarknoten hinausgeschoben. Nun wird solange es einen aktiven Knoten gibt eine PUSH oder RELABEL Operation auf ihm durchgeführt. Aktiv kann jeder Knoten werden, der noch Flussüberschuss hat. Existiert kein aktiver Knoten mehr, so terminiert der Algorithmus und der berechnete Fluss ist ein gültiger und maximaler Fluss.

Das Applet

Das Applet visualisiert die beiden oben genannten Algorithmen. Interessanter ist dabei natürlich der Goldberg & Tarjan Algorithmus, da vielleicht erstmal intuitiv nicht ganz klar ist, dass er tatsächlich einen maximalen Fluss berechnet.

Die Höhe eines Knoten wird über die Größe der Böbbel, bzw. über die erste Zahl in Klammern bei jedem Knoten, dargestellt. Der rote Knoten ist der aktuell aktive Knoten, der vom Algorithmus betrachtet wird. Rosa Knoten haben Flussüberschuss und sind noch ausstehende Kandidaten um aktiv zu werden. Der Wert des Flussüberschusses ist die zweite Zahl in Klammern an jedem Knoten.

An dem Graph "sackgasse" sieht man sehr schön wo der Goldbarg & Tarjan von der Laufzeit seinen Worst-Case erreicht, da er solange versucht Fluss in die Sackgasse vor und zurückzuschieben, bis sich die Knoten alle über die Quelle erhöht haben, und der Fluss endlich in die Quelle zurückfließen kann.

Dein Browser kann leider keine Applets darstellen

Ich habe die Algorithmen nur extrem kurz angerissen und die Beschreibung ist unvollständig. Ein gutes Papier über Flüsse und die beiden Algorithmen ist hier zu finden. Dort werden auch die Laufzeiten sowie die Korrektheit der Algorithmen bewiesen.

Quellcode vom Applet

Hier die wichtigsten Dateien:

Website by: Thomas Pajor, Augartenstr. 56, 76137 Karlsruhe - www.darkviper.de - with help from: flowhase