title: Max-flow-min-cut-stelling
text: 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.<ref>[http://cms.math.ca/10.4153/CJM-1956-045-5 , "Maximal flow through a network", Can. J. Math. (1956), vol. 8, blz. 399-404.]</ref>
  
  De volgende 3 condities zijn equivalent:
    is een maximale flow in 
   Het residuële netwerk  bevat geen augmenterende paden.
    voor elke snede van .
  
  Voorbeeld
  
  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:
  
  {|class="wikitable"
  ! 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.
  
  Grafentheorie