Maximaler Fluss verständlich erklärt

Wie viel Ware passt durch ein Netz aus Werken, Verteilzentren und Filialen, in dem jede Verbindung nur begrenzt trägt? Die Antwort liegt in dem Engpass des Netzes, und ein einfaches Verfahren findet ihn Weg für Weg. Diese Seite erklärt das zuerst ohne Formeln und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen. Zur Seite gehört eine Demo zum Ausprobieren.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Netz, in dem jede Verbindung begrenzt trägt

Stellen Sie sich ein Unternehmen vor, das Ware herstellt und verteilt. Die Werke produzieren, die Verteilzentren sammeln und sortieren, die Filialen verkaufen. Zwischen diesen Orten liegen Verbindungen, etwa Lkw-Linien. Jede ist eine Einbahnstraße, auf der die Ware nur in eine Richtung läuft, und kann je Zeitraum nur eine bestimmte Menge befördern. Diese Obergrenze heißt Kapazität. Auch ein Verteilzentrum schafft nur eine bestimmte Menge, und eine Filiale braucht nur so viel, wie sie verkauft.

Fachleute nennen so etwas ein Flussnetz und die Ware, die hindurchläuft, den Fluss. Um die Frage einfach zu halten, denkt man sich alle Werke an einem gemeinsamen Anfangspunkt zusammengefasst, der Quelle, und alle Filialen an einem gemeinsamen Endpunkt, der Senke. Gefragt ist: Wie viel Ware kann höchstens von der Quelle zur Senke gelangen, und an welcher Stelle liegt der Engpass?

Das ist weniger einfach, als es klingt. Die Ware verteilt sich auf viele Wege, und diese Wege teilen sich Verbindungen. Schickt man auf dem einen Weg viel durch, bleibt für den anderen weniger übrig.

Der Engpass ist eine Linie durch das Netz

Ziehen Sie gedanklich eine Linie durch das Netz, sodass die Quelle auf der einen Seite liegt und die Senke auf der anderen. Alle Ware muss diese Linie überqueren. Mehr, als die Verbindungen zusammen tragen können, die die Linie in Fließrichtung kreuzen, kommt also nie hinüber. Eine solche Linie heißt Schnitt, und die Summe der Kapazitäten der gekreuzten Verbindungen ist seine Kapazität.

Es gibt viele mögliche Linien, und jede liefert eine Obergrenze für die Menge. Die niedrigste davon ist der minimale Schnitt: der eigentliche Engpass. Er kann bei den Filialen liegen, bei den Werken oder irgendwo dazwischen. Der Kern dieser Seite ist ein Satz, der in jedem solchen Netz gilt: Der größte mögliche Fluss und die Kapazität des kleinsten Schnitts sind derselbe Wert. Es bleibt keine Lücke, in der sich noch ein Stück Ware unterbringen ließe.

Wie ein Verfahren den Fluss findet: Weg für Weg

Das Verfahren heißt Edmonds-Karp, nach seinen Erfindern. Es arbeitet in Runden. In jeder Runde sucht es einen Weg von der Quelle zur Senke, auf dem jede Verbindung noch freie Kapazität hat. Es schickt so viel Ware hindurch, wie die engste freie Stelle auf diesem Weg zulässt, und fängt von vorn an. Dabei wählt es immer den Weg mit den wenigsten Stationen; die Suche danach heißt Breitensuche, weil sie zuerst alle nahen Orte absucht und erst dann weiter entfernte.

Manchmal blockiert ein früher gewählter Weg einen besseren. Deshalb darf das Verfahren Ware auch zurücknehmen: Zu jeder Verbindung führt es in seiner Rechnung eine Gegenrichtung, die Rückkante, auf der sich schon geschickte Ware wieder abziehen und über eine andere Strecke umleiten lässt. Ohne diese Möglichkeit kann ein einfaches Auffüllen unter dem größten möglichen Wert hängen bleiben; in der Demo geschieht das bei einem Teil der erzeugten Netze.

Findet die Suche keinen freien Weg mehr, ist der Fluss maximal. Zugleich liefert sie den Beweis: Die Orte, die man von der Quelle aus noch erreicht, liegen auf der einen Seite einer Linie. Alle Verbindungen, die aus diesem Bereich hinaus in den Rest des Netzes führen, sind voll ausgelastet. Verbindungen, die in Gegenrichtung vom Rest des Netzes in diesen Bereich führen, transportieren nichts. Das ist der minimale Schnitt, und seine Kapazität ist genau die Menge, die bereits fließt.

Der Haken des Verfahrens und was Sie mitnehmen

Das Verfahren zählt nur Menge, nicht Geld. Zwei Flüsse mit derselben Gesamtmenge können sehr unterschiedlich teuer sein, weil sie verschiedene Verbindungen nutzen, und das Verfahren hat keine Kenntnis von diesen Kosten. Der Fluss, den es liefert, ist deshalb maximal, aber nicht der billigste dieser Menge. Auch die Zahl der Runden hängt davon ab, wie man den Weg wählt: An einem eigens gebauten Beispiel der Demo braucht eine ungünstige Wahl sehr viele Runden, die Wahl des kürzesten Wegs nur wenige.

Was Sie daraus mitnehmen: Wer wissen will, wie viel ein Netz schafft, sollte nicht jede Verbindung einzeln prüfen, sondern den Engpass suchen, also eine kleinste Linie, die Quelle und Senke trennt. Zusätzliche Kapazität bringt zunächst nur dort etwas; an anderen Stellen bleibt sie ungenutzt. Nach einem Ausbau kann der Engpass an eine andere Stelle wandern, und es kann mehrere gleich enge Linien geben. Dann wirkt ein Ausbau erst, wenn er an allen von ihnen ansetzt, und weiter nur bis ein anderer Engpass greift.

Wie ernst ist das Modell zu nehmen?

Die Demo ist ein stark vereinfachtes Modell mit erzeugten Daten: ein einziges Gut (alle Waren sind gleich), gerechnet in ganzen Einheiten, ein einziger Zeitraum und Netze, die der Zufall aus Werken, Verteilzentren und Filialen baut. Sie zeigt, wie die Mechanik der Verbesserungswege und der Zusammenhang von Fluss und Schnitt wirken, nicht wie ein bestimmtes echtes Verteilnetz aussieht.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Netz: gerichteter Graph \(G=(V,E)\) mit Quelle \(s\), Senke \(t\) und ganzzahligen Kapazitäten \(c_e \ge 0\). Ein Fluss \(f\) erfüllt \(0 \le f_e \le c_e\) und die Flusserhaltung in allen Knoten außer \(s\) und \(t\).
• Vehikel: Quelle → Werke (Kapazität = Werkskapazität) → Verteilzentren (Eingang → Ausgang, Kapazität = Durchsatz) → Filialen → Senke (Kapazität = Nachfrage). Ein Verteilzentrum ist gespalten, weil ein Flussnetz nur Kantenkapazitäten kennt. Standard: 3 Werke, 3 Verteilzentren, 8 Filialen, Netzdichte 60 %, Streuung 50 %, Auslastung 90 %, Breitensuche.
• Wegesuchen: Breitensuche (kürzester Weg, Edmonds-Karp 1972), Tiefensuche (erster gefundener Weg in fester Kantenreihenfolge, Ford-Fulkerson 1956) und breitester Weg (Dijkstra-Variante mit größtem Engpass, ebenfalls Edmonds-Karp 1972).
• Zufall: Alle Zahlen sind ganz, der Zufallsgenerator ist ein eigener SplitMix64 auf Python-Ints statt numpy.random, damit jede Zahl auf Windows und Linux dieselbe ist.

Die Formeln

Der Wert eines Flusses ist der Nettoabfluss an der Quelle, und in jedem Knoten außer \(s\) und \(t\) fließt so viel hinein wie heraus (\(\delta^+(v)\) und \(\delta^-(v)\) sind die Mengen der ausgehenden und eingehenden Kanten):

\[|f|=\sum_{e\in\delta^+(s)}f_e-\sum_{e\in\delta^-(s)}f_e\]

Der Restgraph \(G_f\) hat zu jeder Kante \((u,v)\) eine Vorwärtskante mit Restkapazität \(c_e-f_e\) und eine Rückkante \((v,u)\) mit Restkapazität \(f_e\). Ein Verbesserungsweg ist ein Weg von \(s\) nach \(t\) in \(G_f\); sein Engpass \(\delta\) ist die kleinste Restkapazität auf ihm. Aufgefüllt wird um \(\delta\), auf Vorwärtskanten additiv und auf Rückkanten subtraktiv, der Wert steigt um \(\delta\). Das lineare Programm \(\max\,|f|\) hat als Dual das Min-Cut-Problem.

Satz (Max-Flow = Min-Cut, Ford und Fulkerson): \(f\) ist genau dann maximal, wenn es keinen Verbesserungsweg gibt. Sei \(Z\) die Menge der in \(G_f\) von \(s\) erreichbaren Knoten. Dann ist jede Kante von \(Z\) nach \(\bar Z\) voll und jede von \(\bar Z\) nach \(Z\) leer, also

\[|f|=c(Z,\bar Z)\]

Weil kein Fluss größer sein kann als ein Schnitt (schwache Dualität), ist \(f\) maximal und \(Z\) ein minimaler Schnitt. Bei ganzzahligen Kapazitäten bleibt jeder Fluss ganzzahlig, \(\delta \ge 1\), und das Verfahren endet nach höchstens \(|f^*|\) Wegen. Bei irrationalen Kapazitäten und ungünstiger Wegewahl kann Ford-Fulkerson unendlich laufen, Edmonds-Karp nie.

Edmonds-Karp: Wählt man stets einen Weg mit den wenigsten Kanten, wird die Entfernung \(d_f(s,v)\) jedes Knotens im Lauf des Verfahrens nie kleiner (Lemma). Bei jedem Auffüllen wird mindestens eine Kante kritisch, und sie kann erst wieder kritisch werden, wenn sich ihr Endpunkt um mindestens 2 vom Start entfernt hat, also höchstens \(|V|/2\)-mal. Daraus folgen höchstens \(|E|\cdot|V|/2\) Verbesserungswege und, mit \(O(|E|)\) je Suche, die Laufzeit

\[O(|V|\cdot|E|^2)\]

unabhängig von den Kapazitäten.

Befunde

Jede Zahl steht in tests/test_claims.py der Demo: die Lehrnetze von Hand, die Beispielnetze über ihre Zufalls-Seeds, die Verteilungen über 100 feste Netze (Zufalls-Seeds 100000–100099). Sofern nichts anderes dasteht, gelten sie für die Standardeinstellungen (3 Werke, 3 Verteilzentren, 8 Filialen, Netzdichte 60 %, Streuung 50 %, Auslastung 90 %, Breitensuche). Die Logik rechnet nur mit ganzen Zahlen; die Anteile und Mediane sind deshalb auf jeder Plattform identisch.

Frage	Befund
Wird der Fluss maximal?	Ja, auf jedem getesteten Netz mit jeder der drei Wegesuchen (Breitensuche, Tiefensuche, breitester Weg). Unabhängig gegen networkx (maximum_flow, minimum_cut) und scipy (maximum_flow, beide Verfahren) geprüft, dazu Brute-Force-Aufzählung aller Schnitte auf Kleinstnetzen. Schnittkapazität = Flusswert auf jedem Netz.
Wie viele Wege?	Im Mittel über 100 Netze: 11,1 (Breitensuche), 14,1 (Tiefensuche), 8,2 (breitester Weg). Der breiteste Weg hat die wenigsten, die Tiefensuche die meisten.
Wird die Weglänge nie kürzer?	Bei der Breitensuche auf allen 100 Netzen, bei der Tiefensuche auf nur 5, beim breitesten Weg auf 32 von 100.
Wie nah liegt die Wegezahl an der Schranke?	Bei der Breitensuche im Mittel bei 3,4 %, höchstens bei 5,1 % der Schranke \(|V|\cdot|E|/2\). Bei den kleinsten Netzen sind es 4,7 %, bei den größten getesteten Netzen (166 Knoten) 0,14 %.
Wo liegt der Engpass?	Bei Auslastung 40 % ist die Nachfrage in 88 % der Netze ganz gedeckt, ab 110 % nirgends mehr. Mit steigender Auslastung wandert der Schnitt von den Filialen (Lanes DC → Filiale bei 80 %) zu den Werken (75–80 % der Netze ab 120 %) und den Sammellinien Werk → DC (bis 63 %); der DC-Durchsatz ist in höchstens 20 % der Netze überhaupt beteiligt.
Ist der Engpass eindeutig?	In 80 von 100 Netzen ja; in 20 gibt es mehrere gleich gute minimale Schnitte.
Was, wenn man Rückkanten weglässt?	Ein Greedy-Fluss ohne Rückkanten bleibt in 60 von 100 Netzen unter dem Maximum (Verlust im Mittel 7,1 %, wo er eintritt 11,8 %, im schlimmsten Netz 36 %); der breiteste Weg in 45 von 100. Breitensuche und Tiefensuche liefern ohne Rückkanten dasselbe, weil das Netz geschichtet ist und alle Wege gleich lang sind. Auf dem Lehrnetz „Umleiten nötig“ bleibt die Tiefensuche bei 1 statt 2 stehen.
Und die Kosten?	Die Suche kennt sie nicht: Der Fluss kostet im Median 11,1 % (Breitensuche), 9,9 % (Tiefensuche) und 11,0 % (breitester Weg) mehr als der billigste Fluss gleicher Menge; nur bei 2 von 100 Netzen ist der Breitensuche-Fluss auch kostenoptimal.
Hängt die Rundenzahl an den Kapazitäten?	Nur bei ungünstiger Pfadwahl: Ein Gegenspieler, der in der Raute mit Kapazität M abwechselnd über die Querkante geht, braucht 2M Wege (20 000 bei M = 10 000). Breitensuche und breitester Weg brauchen immer 2, die Tiefensuche in fester Reihenfolge 4.
Wie wächst der Aufwand?	Die durchsuchten Kanten wachsen schneller als die Kantenzahl: Steigung im doppelt logarithmischen Diagramm 1,74 (Breitensuche), 1,72 (Tiefensuche), 1,87 (breitester Weg) von 12 auf 166 Knoten. Gezählt werden durchsuchte Kanten, nie Sekunden.
Zuordnung als Fluss	Fünf Fahrzeuge, fünf Aufträge, Einheitskapazitäten: Flusswert 5 in 5 Wegen, die größtmögliche Paarzahl (gegen das scipy-Matching geprüft).

Grenzen

• Nur die Menge zählt: Die Kosten liegen bei den Standardeinstellungen im Median über dem billigsten Fluss gleicher Menge, weil die Suche nur Restkapazitäten sieht. Das Verfahren dazu, Successive Shortest Paths, ist Thema einer eigenen Demo (ssp-demo).
• Vorab-Hypothesen, die nicht oder nur teilweise stimmten: Die Wegezahl der Breitensuche liegt im ungünstigsten der 100 Netze mit 5,1 % knapp über der erwarteten Marke von 5 %. Der breiteste Weg ist nur bei den Wegen vorn: Bei den durchsuchten Kanten hat im Median die Tiefensuche die wenigsten (426 gegen 461 und 526), obwohl sie die meisten Wege braucht; bei den größten Netzen (166 Knoten) durchsucht der breiteste Weg die meisten Kanten (285 000 gegen 209 000 und 156 000).
• Der Gegenspieler ist Regie, keine Suchregel: Die Tiefensuche in fester Kantenreihenfolge braucht in der Falle nur 4 Wege statt 2M. Der schlimmste Fall verlangt eine ungünstige Wahl; Ford-Fulkerson ist ein Rahmen, kein Algorithmus.
• Synthetische, geschichtete Netze: Alle Daten sind erzeugt, alle Wege von der Quelle zur Senke haben im Vehikel die gleiche Länge. Das erklärt, warum Breiten- und Tiefensuche ohne Rückkanten dasselbe liefern; für andere Netzformen ist das nicht gesagt.
• Ein Gut, ganzzahlig, ein Zeitpunkt: Alle Waren sind gleich, gerechnet wird in ganzen Einheiten. Mehrere Güter auf gemeinsamen Kanten machen den Fluss im Allgemeinen gebrochen, ganzzahlig ist er NP-schwer. Das Netz gilt für eine Periode. Die durchsuchten Kanten wachsen schneller als die Kantenzahl, das ist der Ansatzpunkt von Dinic.
• Die Verteilungen gelten für diese 100 festen Netze bei den genannten Einstellungen, nicht für beliebige Netze.

Quellen

• Ford, L. R., Fulkerson, D. R. (1956): Maximal Flow through a Network (Ford-Fulkerson-Verfahren, Max-Flow-Min-Cut-Satz).
• Edmonds, J., Karp, R. M. (1972): Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems (Breitensuche und breitester Weg).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/edmonds-karp-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die README der Demo nennt nur Autoren und Jahre, die Titel sind nicht gegengeprüft.