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 capaciteit van een s-t-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 gerichte graaf is met knopenverzameling $V$ en bogenverzameling $E$. Elke boog $(u,v)\in E$ heeft een (niet negatieve) capaciteit $c(u,v)$. Er zijn twee bijzondere knopen: de bron (source) $s$ en de uitgang (sink) $t$.

Een s-t-snede is een partitie van de knopenverzameling 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 gelijk aan de som van de capaciteit van de bogen die vertrekken in $S$ en eindigen in $T$:

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

Een stroming in het netwerk is een afbeelding $x:E\to {ℝ}^{+}$, aangeduid als $x_{ij}$, die voldoet aan de voorwaarden:

1. $0\le x_{ij}\le c_{ij}$ voor elke $(i,j)\in E$ (capaciteitsvoorwaarde);
2. $\sum _{j:(i,j)\in E}{x}_{ij}-\sum _{j:(j,i)\in E}{x}_{ji}=0$ (behoud van stroming) voor elke $i\in A\setminus \{s,t\}$; als $i=s$ is deze som gelijk aan $f$ (de bron "produceert" stroming) en als $i=t$ is deze som gelijk aan $-f$ (de uitgang "verbruikt" stroming) voor een zekere $f\ge 0$.

Het maximum-flow-probleem is: vind een $x$ waarvoor $f$ maximaal is. De stelling zegt dat de maximale stroming die kan stromen van de source naar de sink gelijk is aan de minimale capaciteit van alle s-t-sneden van het netwerk. De stelling werd door Ford en Fulkerson in 1956 bewezen; zij ontwikkelden het eerste algoritme om de maximum flow in een netwerk te berekenen.

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. Sjabloon:ISBN. Chapter 26: Maximum Flow, pp.643–700.