Max-Flow-Min-Cut-Theorem

Das Max-Flow-Min-Cut-Theorem ist ein Satz der Graphentheorie über den maximalen Fluss in Flussnetzwerken. Er leitet sich aus Mengers Theorem ab. Er besagt:

Der maximale Fluss im Netzwerk hat genau den Wert dessen minimalen Schnitts.

Anders gesagt, wird der Fluss durch ein Netzwerk durch dessen Flaschenhals beschränkt - auch wenn an anderen Stellen ein größerer Fluss möglich wäre, so ist der Gesamtfluss durch die Engstelle limitiert.

Definitionen

Sei G(V,E) ein endlicher gerichteter Graph und jede Kante (u,v) habe eine zugewiesene nichtnegative Kapazität c(u,v). Des Weiteren gibt es eine Quelle s, in der der Fluss beginnt, und eine Senke t, in der er endet.

Ein Schnitt ist eine Aufteilung der Knoten in zwei disjunkte Teilmengen S und T. Die Kapazität eines Schnittes (S,T) ist die Summe aller Kantenkapazitäten von S nach T, also $c(S,T) = \sum_{u \in S, v \in T | (u,v) \in E} c(u,v)$.

Satz

Die folgenden drei Aussagen sind äquivalent:

1. f ist der maximale Fluss in G.
2. Das Residualnetzwerk G_f enthält keinen augmentierenden Pfad.
3. Für mindestens einen Schnitt (S,T) ist der Wert des Flusses gleich der Kapazität des Schnittes: | f | = c(S,T)

Beweisskizze

• $1 \Rightarrow 2$ Wenn es einen augmentierenden Pfad gäbe, so könnte man den Fluss entlang dessen vergrößern; somit kann der Fluss nicht maximal gewesen sein.

• $2 \Rightarrow 3$ Wenn es keinen augmentierenden Pfad gibt, dann teile den Graph in S, die von s im Residualnetzwerk erreichbaren Knoten, und T, den Rest. Dann ist c(S,T) = 0 (wäre es nicht 0, so wäre T doch erreichbar gewesen). Dann ist für diesen Schnitt | f | = c(S,T).

• $3 \Rightarrow 1$ Wenn f nicht maximal wäre, so könnte man ihn vergrößern. Da f kleiner gleich der Kapazität eines jeden Schnitts ist, kann für mindestens einen Schnitt die Kapazität noch nicht ausgenutzt sein; darüber hinaus gilt | f | = c(S,T) für keinen Schnitt, weil sonst kein augmentierender Pfad für die Flussvergrößerung bestünde und der Fluss maximal wäre.

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 | f | die Größe des kleinsten Schnitts erreicht hat, keinen augmentierenden Pfad mehr enthalten kann.

Beispiel

Ein Netzwerk mit maximalem Fluss und drei minimalen Schnitten

Sei das Flussnetzwerk mit den Knoten V = {s,o,p,q,r,t} gegeben, und ein maximaler Fluss von der Quelle s zur Senke t der Größe 5.

Es gibt drei minimale Schnitte in diesem Netzwerk:

Schnitt	Kapazität
S = {s,p},T = {o,q,r,t}	c(s,o) + c(p,r) = 3 + 2 = 5
S = {s,o,p},T = {q,r,t}	c(o,q) + c(p,r) = 3 + 2 = 5
S = {s,o,p,q,r},T = {t}	c(q,t) + c(r,t) = 2 + 3 = 5

Anmerkung: S = {s,o,p,r},T = {q,t} ist kein minimaler Schnitt, obwohl (o,q) und (r,t) voll genutzt werden; denn es gibt im Residualnetzwerk G_f noch eine Kante (r,q) der Restkapazität c_f(r,q) = c(r,q) − f(r,q) = 0 − ( − 1) = 1.

Geschichte

Das Theorem wurde 1956 von Peter Elias, Amiel Feinstein und Claude Elwood Shannon bewiesen, und unabhängig davon auch von Lester Randolph Ford junior und Delbert Ray Fulkerson im selben Jahr.

Siehe auch

• Algorithmus von Ford und Fulkerson

Weblinks

• Max-Flow Min-Cut Animation (englisch)
• Max-Flow Problem: Ford-Fulkerson Algorithm (englisch)

Einzelnachweise

• P. Elias, A. Feinstein und Claude Elwood Shannon: Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, 117—119, 1956.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein: Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 26: Maximum Flow, pp.643–700.