Maximaler-Fluss-Rechner
Edmonds-Karp · Augmentierender Pfads · Min-Cut · Fluss Visualization
Finde den maximalen Fluss von der Quelle zur Senke in einem gerichteten Kapazitätsnetzwerk. Verwendet den Edmonds-Karp-Algorithmus (BFS Ford-Fulkerson, O(VE²)) mit schrittweisen augmentierenden Pfaden und Canvas-Visualisierung.
Schnellbeispiele
Unterstützte Formate: S A 10 S→A:10 S-A-10
Ergebniszusammenfassung
Minimaler Schnitt (Max-Fluss-Min-Schnitt-Theorem)
Der minimale Schnitt trennt Quelle und Senke. Seine Gesamtkapazität entspricht dem maximalen Fluss.
Augmentierende Pfade — Schritt für Schritt
| Schritt | Augmentierender Pfad | Engpass | Kumulativer Fluss |
|---|
Fluss auf jeder Kante
Rot = gesättigt (Fluss = Kapazität). Grau = ungenutzt (Fluss = 0).
| Kante | Kapazität | Fluss | Verbleibend | Status |
|---|
Flussnetzwerk-Visualisierung
Kante labels show flow/capacity. Green = has flow, Red = saturated, Gray = unused. Source = green node, Sink = red node.
Was ist das Maximum-Fluss-Problem?
The maximum flow problem is one of the most fundamental problems in combinatorial optimization and network theory. Given a gerichtet graph where each edge has a non-negative capacity — the maximum amount of flow it can carry — the goal is to determine the greatest total flow that can be routed from a designated source node to a designated sink node, subject to two constraints: flow on each edge must not exceed its capacity, and flow must be conserved at every intermediate node (inflow equals outflow).
Fluss networks appear throughout science and engineering. Water flowing through pipes, data packets through Internet routers, goods through supply chains, cars through road networks — all can be modeled as flow networks. The maximum flow then represents the network's throughput capacity.
Ford-Fulkerson-Methode
Die Ford-Fulkerson-Methode ist der grundlegende Ansatz zur Lösung von Max-Fluss-Problemen. Die Methode unterhält einen Residualgraph. In jedem Schritt findet sie einen augmentierenden Pfad von der Quelle zur Senke im Residualgraph und schiebt so viel Fluss wie möglich entlang dieses Pfades.
Ford-Fulkerson is a method, not a specific algorithm, because it does not specify how to find augmenting paths. Different search strategies yield different algorithms with different complexity guarantees. With DFS, the number of Iterationen can be exponential on graphs with irrational capacities. With BFS, the Edmonds-Karp algorithm achieves polynomial time.
Edmonds-Karp-Algorithmus
Der Edmonds-Karp-Algorithmus implementiert Ford-Fulkerson unter Verwendung der Breitensuche (BFS), um bei jeder Iteration den kürzesten augmentierenden Pfad (wenigste Kanten) zu finden. Diese einfache Modifikation bietet eine entscheidende Komplexitätsgarantie:
- Jede BFS findet den kürzesten Pfad in O(V + E) Zeit.
- The total number of augmenting path Iterationen is bounded by O(VE).
- Overall time complexity: O(VE²) where V = Eckpunkte, E = edges.
This polynomial bound makes Edmonds-Karp highly practical. For example, a network with 50 nodes and 200 edges would need at most 50 × 200 = 10,000 BFS Iterationen — entirely feasible.
Residualgraph und augmentierende Pfade
Ein Residualgraph erfasst, wie viel zusätzlicher Fluss entlang jeder Kante gesendet werden kann. Für jede ursprüngliche Kante (u → v) mit Kapazität c und aktuellem Fluss f hat der Residualgraph:
- Eine Vorwärtskante (u → v) mit Residualkapazität c − f (verbleibender Platz).
- Eine Rückwärtskante (v → u) mit Residualkapazität f (ermöglicht das Abbrechen des Flusses).
The backward edges are the key insight: they let the algorithm "undo" suboptimal routing decisions found in earlier Iterationen, effectively allowing it to reroute flow through better paths.
Ein augmentierender Pfad ist jeder Pfad von der Quelle zur Senke im Residualgraph, bei dem alle Kanten eine positive Residualkapazität haben.
Max-Fluss-Min-Schnitt-Theorem
The Max-Fluss Min-Cut theorem is a landmark result stating that for any flow network, the maximum flow equals the minimum cut capacity. A cut is a partition of the nodes into two sets S (containing the source) and T (containing the sink); its capacity is the sum of capacities of edges going from S to T. The minimum cut is the cut with smallest total capacity.
Diese Dualität hat tiefgreifende Auswirkungen: Das Finden des maximalen Flusses deckt gleichzeitig den Engpass des Netzwerks (den minimalen Schnitt) auf.
Anwendungen
Der maximale Fluss ist einer der am häufigsten angewandten Algorithmen in der Informatik und im Operations Research:
- Internet-Routing: Maximierung des Datendurchsatzes zwischen Netzwerkknoten.
- Bipartites Matching: Jobplanung, Zuweisungsprobleme reduzieren sich auf maximalen Fluss.
- Bildsegmentierung: Graph-Cut-Methoden verwenden minimale Schnitte, um Vordergrund vom Hintergrund zu trennen.
- Supply-Chain-Optimierung: Routing von Gütern durch Vertriebsnetzwerke zur Maximierung des Durchsatzes.
- Projektplanung: Ressourcenbeschränkte Analyse des kritischen Pfades über Netzwerkfluss.
- Sport-Eliminierung: Die Bestimmung, ob ein Team noch eine Liga gewinnen kann, verwendet maximalen Fluss.
- Netzwerkzuverlässigkeit: Identifizierung kritischer Verbindungen, deren Entfernung die Netzwerkkapazität am stärksten reduziert.