Max-flow-min-cut-stelling

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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\colon E \to \mathbb{R}^+, 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.[1]

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[bewerken]

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[bewerken]

Referenties[bewerken]

Bronnen, noten en/of referenties