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 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:
- voor elke (capaciteitsvoorwaarde);
- (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:
- is een maximale flow in
- Het residuële netwerk bevat geen augmenterende paden.
- voor elke snede van .
Voorbeeld
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/94/Max_flow.svg/260px-Max_flow.svg.png)
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
- 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.
- ↑ 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.