Max-flow-min-cut-stelling

De max-flow-min-cut-stelling is een stelling in de optimalisatietheorie over de maximum flow in netwerken. Hij is afgeleid van de Stelling van Menger. De stelling luidt: De maximale hoeveelheid van flow is gelijk aan de minimale snede.

Informeel zegt de stelling dat de maximale flow in een netwerk bepaald wordt door de 'bottleneck': het is onmogelijk dat er tussen twee knopen meer data stroomt dan de zwakste verbinding ergens tussen deze twee knopen.

Definitie

Stel dat $G(V,E)$ een eindige graaf is en elke boog $(u,v)$ heeft een (niet negatieve) capaciteit $c(u,v)$. Stel daarenboven dat voor elke twee knopen de bron $s$ en de uitgang $t$ verschillend zijn.

Een snede is een opsplitsing in 2 verzamelingen $S$ en $T$ zodat $s$ zich in $S$ bevindt en $t$ zich in $T$ bevindt. Er zijn zo $2^{|V|-2}$ dergelijke deelverzamelingen van een graaf. De capaciteit van een snede $(S,T)$ is

$c(S,T) = \sum_{u \in S, v \in T | (u,v) \in E} c(u,v)$,

Dit is de som van alle capaciteiten van alle bogen die de snede overschrijden, van de regio $S$ naar de regio $T$.

De volgende 3 condities zijn equivalent:

1. $f$ is een maximale flow in $G$
2. Het residuële netwerk $G_f$ bevat geen augmenterende paden.
3. $|f| = c(S,T)$ voor elke snede van $(S,T)$.

Voorbeeld

Een netwerk met maximale flow, en 3 minimale snedes.

Beschouwen we een netwerk met de knopen $V=\{s,o,p,q,r,t\}$, en een totale flow van de bron $s$ naar de uitgang $t$ van 5, dat het maximale is in dit netwerk.

Er zijn 3 minimale snedes in dit netwerk:

Snede	Capaciteit
$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$

Bemerk dat $S=\{s,o,p,r\},T=\{q,t\}$ geen minimale snede is, zelfs als beide $(o,q)$ en $(r,t)$ gesatureerd zijn in de gegeven flow. Dit doordat in het residuële netwerk $G_f$ er een boog (r,q) bestaat met capaciteit $c_f(r,q) = c(r,q)-f(r,q)=0-(-1)=1$.

Externe links

• A review of current literature on computing maximum flows
• Max-Flow Min-Cut Animation
• Max-Flow Problem: Ford-Fulkerson Algorithm

Referenties

• P. Elias, A. Feinstein, and C. E. 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, and 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.