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

Een s-t-snede is een partitie van de knopenverzameling in 2 verzamelingen ${\displaystyle S}$ en ${\displaystyle T}$ zodat ${\displaystyle s}$ zich in ${\displaystyle S}$ bevindt en ${\displaystyle t}$ zich in ${\displaystyle T}$ bevindt. Er zijn zo ${\displaystyle 2^{|V|-2}}$ dergelijke deelverzamelingen van een graaf.

De capaciteit van een snede ${\displaystyle (S,T)}$ is gelijk aan de som van de capaciteit van de bogen die vertrekken in ${\displaystyle S}$ en eindigen in ${\displaystyle T}$:

${\displaystyle 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 ${\displaystyle x\colon E\to \mathbb {R} ^{+}}$, aangeduid als ${\displaystyle x_{ij}}$, die voldoet aan de voorwaarden:

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

Het maximum-flow-probleem is: vind een ${\displaystyle x}$ waarvoor ${\displaystyle 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.^[1]

De volgende 3 condities zijn equivalent:

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

Voorbeeld

Een netwerk met maximale flow, en 3 minimale snedes.

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

Er zijn 3 minimale snedes in dit netwerk:

Snede	Capaciteit
${\displaystyle S=\{s,p\},T=\{o,q,r,t\}}$	${\displaystyle c(s,o)+c(p,r)=3+2=5}$
${\displaystyle S=\{s,o,p\},T=\{q,r,t\}}$	${\displaystyle c(o,q)+c(p,r)=3+2=5}$
${\displaystyle S=\{s,o,p,q,r\},T=\{t\}}$	${\displaystyle c(q,t)+c(r,t)=2+3=5}$

Bemerk dat ${\displaystyle S=\{s,o,p,r\},T=\{q,t\}}$ geen minimale snede is, zelfs als beide ${\displaystyle (o,q)}$ en ${\displaystyle (r,t)}$ gesatureerd zijn in de gegeven flow. Dit doordat in het residuële netwerk ${\displaystyle G_{f}}$ er een boog (r,q) bestaat met capaciteit ${\displaystyle 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.

Bronnen, noten en/of referenties

1. L.R. Ford en D.R. Fulkerson, "Maximal flow through a network", Can. J. Math. (1956), vol. 8, blz. 399-404. Gearchiveerd op 22 mei 2018.