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 een eindige gerichte graaf is met knopenverzameling en bogenverzameling . Elke boog heeft een (niet negatieve) capaciteit . Er zijn twee bijzondere knopen: de bron (source) en de uitgang (sink) .

Een s-t-snede is een partitie van de knopenverzameling in 2 verzamelingen en zodat zich in bevindt en zich in bevindt. Er zijn zo dergelijke deelverzamelingen van een graaf.

De capaciteit van een snede is gelijk aan de som van de capaciteit van de bogen die vertrekken in en eindigen in :

,

Een stroming in het netwerk is een afbeelding , aangeduid als , die voldoet aan de voorwaarden:

  1. voor elke (capaciteitsvoorwaarde);
  2. (behoud van stroming) voor elke ; als is deze som gelijk aan (de bron "produceert" stroming) en als is deze som gelijk aan (de uitgang "verbruikt" stroming) voor een zekere .

Het maximum-flow-probleem is: vind een waarvoor 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. is een maximale flow in
  2. Het residuële netwerk bevat geen augmenterende paden.
  3. voor elke snede van .

Voorbeeld[bewerken]

Een netwerk met maximale flow, en 3 minimale snedes.

Beschouwen we een netwerk met de knopen , en een totale flow van de bron naar de uitgang van 5, dat het maximale is in dit netwerk.

Er zijn 3 minimale snedes in dit netwerk:

Snede Capaciteit

Bemerk dat geen minimale snede is, zelfs als beide en gesatureerd zijn in de gegeven flow. Dit doordat in het residuële netwerk er een boog (r,q) bestaat met capaciteit .

Externe links[bewerken]

Referenties[bewerken]