Loading AI tools
mathematischer Satz Aus Wikipedia, der freien Enzyklopädie
Auf dem Gebiet der Graphentheorie bezeichnet das Max-Flow-Min-Cut-Theorem einen Satz, der eine Aussage über den Zusammenhang von maximalen Flüssen und minimalen Schnitten eines Flussnetzwerkes gibt. Der Satz besagt:
Der Satz ist eine Verallgemeinerung des Satzes von Menger. Er wurde im Jahr 1956 unabhängig von L.R. Ford Jr. und D.R. Fulkerson, sowie von P. Elias, A. Feinstein und C.E. Shannon bewiesen.[1][2]
Sei ein endlicher gerichteter Graph mit den Knoten und den Kanten . Jede Kante vom Knoten zum Knoten habe eine nichtnegative Kapazität Außerdem gibt es einen Quellknoten , in dem der Netzwerkfluss beginnt, und einen Zielknoten , in dem der Netzwerkfluss endet.
Ein Schnitt ist eine Aufteilung der Knoten in zwei disjunkte Teilmengen und für die gilt, und . Die Kapazität eines Schnittes ist die Summe aller Kantenkapazitäten von nach , also
Die folgenden drei Aussagen sind äquivalent:
Insbesondere zeigt dies, dass der maximale Fluss gleich dem minimalen Schnitt ist: Wegen 3. hat er die Größe mindestens eines Schnitts, also mindestens des kleinsten, und wegen 2. auch höchstens diesen Wert, weil das Residualnetzwerk bereits wenn die Größe des kleinsten Schnitts erreicht hat, keinen augmentierenden Pfad mehr enthalten kann.
Sei das Flussnetzwerk mit den Knoten gegeben, und ein maximaler Fluss von der Quelle zur Senke der Größe 5.
Es gibt drei minimale Schnitte in diesem Netzwerk:
Schnitt | Kapazität |
---|---|
Anmerkung: Bei allen anderen Schnitten ist die Summe der Kapazitäten (nicht zu verwechseln mit dem Fluss) der ausgehenden Kanten größer gleich 6. Zum Beispiel ist kein minimaler Schnitt, da die Summe der Kapazitäten der ausgehenden Kanten gleich ist. Des Weiteren ist kein minimaler Schnitt, obwohl und voll genutzt werden; denn es gibt im Residualnetzwerk noch eine Kante (r,q) der Restkapazität .
Es gibt verschiedene Algorithmen zum Finden minimaler Schnitte. Der folgende Algorithmus findet die Kanten eines minimalen Schnittes direkt aus dem Residualnetzwerk und macht sich damit die Eigenschaften des Max-Flow-Min-Cut-Theorems zu Nutze. Der Restflussgraph kann zum Beispiel mit Hilfe des Algorithmus von Ford und Fulkerson erzeugt werden.
ein endlicher gerichteter Graph mit einer Quelle , einer Senke und jede Kante habe eine nichtnegative Kapazität. findeKantenEinesMinCut() 1 Residualnetzwerk() 2 3 4 Für jeden Knoten 5 Wenn Pfad() in existiert 6 dann 7 ansonsten 8 9 Für jede Kante 10 Wenn startKnoten() und endKnoten() liegt 11 dann 12 ist jetzt die Menge der Kanten für einen minimalen Schnitt
würde im oberen Beispiel die Schnittkanten von enthalten.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.