Netzwerkfluss-Rechner (Maximaler Fluss)

Netzwerkfluss-Rechner (Maximaler Fluss)

Der Netzwerkfluss-Rechner für maximalen Fluss berechnet den maximalen Fluss von einer gewählten Quelle s zu einer gewählten Senke t in einem beliebigen gerichteten Kapazitätsnetzwerk. Er verwendet die Ford-Fulkerson-Methode mit vergrößernden Pfaden via Breitensuche (Edmonds-Karp-Algorithmus) und zeichnet jeden gefundenen Pfad auf, sodass Sie den Entscheidungsprozess Schritt für Schritt nachvollziehen können. Die Ergebnisseite zeigt zudem den Min-Cut – die Engpass-Partition, die beweist, dass Ihr Flusswert optimal ist.

Was ist das Problem des maximalen Flusses?

Ein Flussnetzwerk ist ein gerichteter Graph G = (V, E) mit einer Kapazitätsfunktion c: E → ℝ_≥0. Zwei Knoten sind besonders: die Quelle s (Ursprung des Flusses) und die Senke t (Verbraucher). Ein Fluss f ist eine Zuweisung f(u, v) ≥ 0 auf Kanten, die folgende Regeln erfüllt:

Das Problem des maximalen Flusses sucht den Fluss f, der |f| maximiert. Bildlich gesprochen: Wenn die Kanten Wasserrohre mit bestimmten Kapazitäten wären, wie viele Liter pro Sekunde können Sie maximal von s nach t transportieren?

Wie der Algorithmus funktioniert — Ford-Fulkerson mit BFS

Der Algorithmus führt neben dem aktuellen Fluss einen Residualgraphen. Für jede Kante (u, v) mit Kapazität c und Fluss f enthält dieser:

• eine Vorwärts-Residualkante (u, v) mit Kapazität c − f (Restkapazität) und
• eine Rückwärts-Residualkante (v, u) mit Kapazität f (stornierbarer Fluss).

In jeder Iteration wird eine Breitensuche (BFS) von s nach t im Residualgraphen durchgeführt. Wird ein Pfad gefunden, wird die kleinste Kapazität auf diesem Pfad – der Engpass – zum Fluss jeder Vorwärtskante addiert und von jeder Rückwärtskante abgezogen. Dies nennt man vergrößernden Pfad. Wenn t nicht mehr erreichbar ist, ist der Fluss optimal.

Die Nutzung von BFS macht Ford-Fulkerson zum Edmonds-Karp-Algorithmus mit einer garantierten Laufzeit von O(V · E²). Dies stellt die Terminierung auch bei irrationalen Kapazitäten sicher.

Das Max-Flow-Min-Cut-Theorem

Ein Schnitt (Cut) ist eine Zerlegung der Knoten in zwei Mengen (S, T) mit s ∈ S und t ∈ T. Seine Kapazität ist die Summe der Kapazitäten aller Kanten, die von S nach T führen:

Das Max-Flow-Min-Cut-Theorem (Ford & Fulkerson, 1956) besagt:

Dieses Tool findet den Min-Cut automatisch. Nach Abschluss von Edmonds-Karp wird eine letzte BFS von s im Residualgraphen gestartet; die erreichten Knoten bilden S, die restlichen T. Die Kapazitäten der Kanten, die von S nach T führen, ergeben exakt den Max-Flow-Wert.

Funktionen für das Lernen

• Schritt-für-Schritt Animation. Spielen Sie jeden vergrößernden Pfad mit Play, Pause und Einzelschritten ab. Sehen Sie, welchen Pfad die BFS gewählt hat und wie der Gesamtfluss gewachsen ist.
• Drei synchronisierte Matrizen. Wechseln Sie zwischen der Kapazitätsmatrix C, der Flussmatrix f und der Residualmatrix C − f.
• Min-Cut Partitionsansicht. S-Seite und T-Seite werden als Chips aufgelistet, wobei die gesättigten Schnittkanten rot markiert sind.
• Detaillierte Kantentabelle. Für jede Kante: Kapazität, Fluss, Restkapazität und Auslastungsbalken.
• Geschichtetes Layout. Die Graphenzeichnung basiert auf BFS-Distanzen zur Quelle, sodass das Wasser visuell von links nach rechts fließt – genau wie in Lehrbüchern.

Eingabeformate

1. Kantenliste mit Kapazitäten

Eine Kante pro Zeile. Die Pfeilform ist am besten lesbar, aber Alternativen funktionieren auch:

Ebenfalls akzeptiert: A, B, 10 · A B 10 · A -> B , 10. Mehrere Kanten zwischen denselben Knoten werden summiert.

2. Kapazitätsmatrix

Eine Zeile pro Textzeile, Werte durch Leerzeichen oder Kommas getrennt. Der Eintrag C[i][j] ist die Kapazität von Knoten i nach Knoten j. Nutzen Sie 0 für "keine Kante". Die Matrix muss quadratisch sein und die Diagonale muss 0 sein.

Geben Sie die Knotennamen im Feld Matrix-Bezeichnungen an. Falls weggelassen, werden standardmäßig S, A, B, …, T verwendet.

Anwendungen des maximalen Flusses

Rechenbeispiel

Das "Lehrbuch"-Schnellbeispiel nutzt ein 6-Knoten-Netzwerk mit Quelle S und Senke T. Edmonds-Karp findet vier vergrößernde Pfade:

1. S → A → B → T mit Engpass 4. Laufende Summe: 4.
2. S → A → D → T mit Engpass 6. Laufende Summe: 10.
3. S → C → D → T mit Engpass 4. Laufende Summe: 14.
4. S → C → D → B → T mit Engpass 5. Laufende Summe: 19.

Danach existiert kein Pfad mehr. Der Min-Cut ist (S = {S, C}, T = {A, B, D, T}) mit den Schnittkanten S → A (10) und C → D (9). Die Summe ist 19 – exakt der maximale Fluss.

So verwenden Sie diesen Rechner

1. Eingabeformat wählen – Kantenliste (empfohlen) oder Kapazitätsmatrix.
2. Netzwerk eingeben. Modifizieren Sie ein Beispiel oder geben Sie eigene Daten ein.
3. Quelle und Senke festlegen (oder leer lassen für Automatik).
4. Auf Max-Fluss berechnen klicken. Sie erhalten den Flusswert, den Min-Cut, die Visualisierung und alle Pfade.
5. Animation starten. Nutzen Sie die Steuerung unter dem Graphen, um die Entscheidungsschritte des Algorithmus zu visualisieren.

Limits

• Knoten: bis zu 30 – für optimale Lesbarkeit.
• Kanten: bis zu 200.
• Kapazitäten: nicht-negativ, bis 10⁹. Dezimalzahlen sind erlaubt.
• Keine Selbstschleifen. Diese werden im Standardmodell nicht berücksichtigt.

Häufig gestellte Fragen (FAQ)

Was ist das Problem des maximalen Flusses?

Gegeben ist ein gerichtetes Netzwerk, in dem jede Kante eine nicht-negative Kapazität hat. Das Problem des maximalen Flusses fragt: Wie viel Fluss kann von einem Quellknoten s zu einem Senkenknoten t geleitet werden, wobei der Fluss auf jeder Kante seine Kapazität nicht überschreiten darf und der Zufluss in jeden Knoten (außer Quelle und Senke) dem Abfluss entsprechen muss? Die Antwort ist der maximale Flusswert.

Was ist die Ford-Fulkerson-Methode?

Ford-Fulkerson ist ein allgemeines Verfahren zur Berechnung des maximalen Flusses. Es findet wiederholt einen vergrößernden Pfad von der Quelle zur Senke im Residualgraphen und schickt so viel Fluss wie möglich entlang dieses Pfades (die Engpasskapazität) und aktualisiert dann den Residualgraphen. Das Verfahren endet, wenn kein vergrößernder Pfad mehr existiert. Wird Breitensuche (BFS) zur Pfadauswahl genutzt, heißt es Edmonds-Karp-Algorithmus und läuft in O(V · E²) Zeit.

Was ist der Min-Cut eines Flussnetzwerks?

Ein Schnitt (Cut) ist eine Partition der Knoten in zwei Mengen S und T, sodass die Quelle in S und die Senke in T liegt. Die Kapazität des Schnitts ist die Summe der Kapazitäten der Kanten von S nach T. Ein Min-Cut ist ein Schnitt mit minimaler Kapazität. Das berühmte Max-Flow-Min-Cut-Theorem beweist, dass der maximale Flusswert immer der minimalen Schnittkapazität entspricht, sodass man mit der Suche nach dem einen automatisch den anderen Wert erhält.

Was ist der Residualgraph?

Der Residualgraph hält fest, wie viel zusätzlicher Fluss noch über jede Kante geschickt werden kann. Für jede ursprüngliche Kante (u, v) mit Kapazität c und aktuellem Fluss f enthält der Residualgraph eine Vorwärtskante (u, v) mit Kapazität c minus f (Restkapazität) und eine Rückwärtskante (v, u) mit Kapazität f (stornierbarer Fluss). Ein vergrößernder Pfad nutzt Kanten des Residualgraphen, was es dem Algorithmus ermöglicht, frühere Entscheidungen rückgängig zu machen.

Warum nutzt das Tool BFS für vergrößernde Pfade?

Die Wahl von vergrößernden Pfaden mittels Breitensuche (Edmonds-Karp) garantiert eine Terminierung in polynomialer Zeit, unabhängig von den Kantenkapazitäten. Das einfache Ford-Fulkerson-Verfahren mit beliebiger Pfadstrategie kann bei ungünstigen Eingaben exponentiell viele Iterationen benötigen und bei irrationalen Kapazitäten eventuell gar nicht terminieren. BFS liefert zudem die kürzesten vergrößernden Pfade, die einfacher zu verstehen sind.

Was bedeutet eine gesättigte Kante?

Eine Kante ist gesättigt, wenn ihr Fluss ihrer Kapazität entspricht, sodass kein weiterer Fluss darüber geschickt werden kann. Gesättigte Kanten sind die Engpässe des Netzwerks, und jeder Min-Cut besteht ausschließlich aus gesättigten Kanten, die von der S-Seite zur T-Seite des Schnitts führen. Das Tool markiert gesättigte Kanten rot, damit Sie die Engpassstruktur sofort erkennen können.

Weiterführende Links

• Max-Flow-Min-Cut-Theorem — Wikipedia
• Ford-Fulkerson-Algorithmus — Wikipedia
• Edmonds-Karp-Algorithmus — Wikipedia