Beim Problem Maximaler Fluss in Flussnetzwerken geht es darum, möglichst viel einer Resource von einem Startknoten \(s\) zu einem Zielknoten \(t\) durch ein Netzwerk zu leiten, in dem jede Kante eine endliche Kapazität hat. Als konkretes Beispiel (aus dem Winter 2022) könnte der Startknoten ein Flüssiggasterminal, der Zielknoten eine große Chemiefabrik und die Kanten Gaspipelines sein.

Angenommen, jede Kante kann eine Einheit leiten; wieviel Einheiten Erdgas können wir von \(s\) nach \(t\) leiten? Hier ist eine Möglichkeit, entlang dreier kantendisjunkter Pfade insgesamt drei Einheiten Erdgas zu leiten. Es ist zu beachten, dass die Kapazität der Knotenpunkte unbeschränkt ist.

Ist das optimal? Immerhin können wir die obige Lösung nicht "direkt" verbessern. Der blaue, rote und grüne Pfad blockieren zusammen alle Wege von \(s\) nach \(t\). Wie können wir aber überprüfen, ob es nicht doch eine bessere, vielleicht ganz anders aussehende Lösung gibt? Eine Möglichkeit ist, das Netzwerk zu zerstören, nur in Gedanken natürlich, indem wir ein paar Kanten löschen, sodass \(s\) und \(t\) nicht mehr verbunden sind:

Wenn wir diese vier Kanten zerstören, dann gibt es keinen Pfad mehr von \(s\) nach \(t\). Anders ausgedrückt: jeder \(s-t\)-Pfad muss eine dieser vier Kanten passieren. Es ist also klar, dass wir nicht mehr als vier Einheiten Erdgas leiten können. Die optimale Menge liegt also irgendwo zwischen 3 und 4. Wahrscheinlich haben Sie implizit angenommen, dass es sich bei der Antwort um eine natürliche Zahl handeln muss, dass also z.B. 3,5 gar nicht als Optimum in Frage kommt. Dies stimmt in diesem konkreten Beispiel, ist aber nicht ganz offensichtlich. Hier ist die optimale Lösung, die 4 Einheiten leitet:

Im Allgemeinen werden nicht alle Kanten die gleiche Kapazität haben und werden auch nicht notwendigerweise in beide Richtungen passierbar sein. Ein Netzwerk wird also eher so aussehen:

und ein Fluss darin zum Beispiel so:

Beachten Sie, dass in den Knoten in der Mitte von links \(1 + 0.5\) Einheiten hineinfließen und nach rechts \(0.9 + 0.6\) Einheiten hinaus. Der Fluss lässt sich also nicht unbedingt immer fein säuberlich in Pfade aufteilen. Wenn es sich aber um eine beliebig teilbare Resource handelt wie zum Beispiel ein Gas oder eine Flüssigkeit, dann ist dies ja durchaus realistisch.

Es stellt sich heraus, dass es oft bequemer ist, mit einer leicht veränderten Definition zu arbeiten: die Kapazitätsfunktion \(c\) ist einfach eine Funktion \(V \times V \rightarrow \R^+_0\), und die (gerichteten) Kanten des Netzwerkes sind einfach die Paare \((u,v)\), für die \(c(u,v) > 0\) gilt. Die Kapazitätsfunktion \(c\) kodiert also bereits den zugrundeliegenden Graphen. Hier ist also unsere alternative Definition:

Wenn wir mathematisch-formal über Flussnetzwerke räsonnieren, dann ist die zweite Definition vorzuziehen. Wenn wir aber Beispiele zeichnen oder einen Algorithmus implementieren wollen, dann ist sie womöglich ineffizient: da \(c : V \times V \rightarrow \R^+_0\) ist, müssen wir \(\Theta(n^2)\) Zahlen speichern; eventuell hat unser Netzwerk aber weitaus weniger Kanten; daher ist für Implementierungszwecke die erste Definition vorzuziehen, da wir hier mit einem Speicherplatz von \(\Theta(m)\) auskommen.

Probieren wir nun, Netzwerkflüsse formal zu definieren. Ein Fluss \(f\) ist erst einmal eine Funktion \(f: V \times V \rightarrow \R\). Die Idee ist, dass \(f(u,v)\) angibt, wieviele Einheiten wir entlang der Kante \( (u,v) \) leiten. Dieser Betrag darf natürlich nicht die Kapazität überschreiten. Dies führt uns zu der ersten Bedingung: \(f(u,v) \leq c(u,v)\). Zweitens sollte \(f(u,v) \geq 0\) gelten, da negative Werte ja keinen Sinn machen. Diese zwei Bedingungen zusammen heißen nun auch, dass Fluss nur entlang einer Kante fließen darf: wenn es von \(u\) nach \(v\) keine Kante gibt, also \( (u,v) \not \in E\), dann ist ja \(c(u,v) = 0\) nach der zweiten Definition von Flussnetzwerken, und somit ist \(f(u,v) = 0\) der einzig mögliche Wert. Als dritte Bedingung kommt noch Flusserhalt hinzu: was in \(u\) hineinfließt, muss auch wieder herausfließen, also \( \sum_{v: (v,u) \in E} f(v,u) = \sum_{w: (u,w) \in E} f(u,w)\). Diese Bedingung gilt an allen Knoten außer \(s\) und \(t\); wir wollen ja, dass im Netto Resourcen nach \(t\) hineinfließen.

Schiefsymmetrie-Konvention

Wir können unser Leben mit einem kleinen Trick weitaus einfacher machen. Wir "verlangen" einfach, dass \(f (u,v) = -f(v,u)\) gilt, die Funktion \(f\) also schiefsymmetrisch (auf Englisch skew-symmetric) ist. Die Aussage wir leiten -2 Einheiten Erdgas von \(A\) nach \(B\) hieße also, dass wir 2 Einheiten von \(B\) nach \(A\) leiten. Diese Konvention ist zum Beispiel auch in elektrischen Netzwerken üblich (Kirchhoffsche Regeln). Mit dieser Konvention können wir Flusserhalt ganz kompakt schreiben: \(\sum_{v \in V} f(u,v) = 0\). Hier ist nun unsere vollständige Definition von Netzwerkflüssen:

Aus der Schiefsymmetrie folgt auch sofort, dass \(f(u,u) = 0\) gilt, dass es also keinen Fluss von \(u\) zu sich selbst geben kann. Wenn Sie über Flüsse räsonnieren und sich über etwas nicht im Klaren sind, halten Sie sich an die axiomatische Definition von Flüssen. Dann wird schnell klar werden, ob etwas erlaubt ist oder nicht. Betrachten wir beispielsweise folgendes Netzwerk mit Fluss:

Dies ist definitiv ein "seltsamer" Fluss; es fließen drei Einheiten aus \(s\) über eine Kante heraus, eine Einheit über eine andere aber wieder hinein. Ähnliches spielt sich bei \(t\) ab; schließlich haben wir auch noch einen "Kreisverkehr" in der Mitte des Netzwerkes. Sie mögen dies als unrealistisch, verschwenderisch oder redundant tadeln. Es ist aber alles konform mit den Flussaxiomen, die wir oben ausgearbeitet haben, und daher sehen Sie hier in der Tat einen legalen Fluss. Der Wert dieses Flusses? Der ist 2. In der Summe \(\sum_{v} f(s,v)\) haben Sie eine 3, eine -1 und ganz viele Nullen.