\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \)

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.