h.hofstede (h.hofstede@hogeland.nl)

Max-Flow, Min-Cut
       
De vorige les eindigden we met de stelling  "maximale stroomwaarde  ≤  minimale capaciteit snede".

Deze les zullen we zien dat het gelijkteken geldt, en tegelijkertijd zullen we een manier vinden om een optimale stroom door een netwerk te vinden.

Eerst (uiteraard) de gebruikelijke termen.
Een stroom in een netwerk is een functie die aan elke verbindingslijn een waarde toekent (zie vorige les; er zijn twee voorwaarden). Zo'n stroom geven we vanaf nu aan met de functie f  (van flow) en verbindingslijnen met een v 
Dus:  stroom = f(v)
Een verbindingslijn heet f-verzadigd als  f(v) = c(v),  waarbij c de capaciteit van lijn v is.  Als  f(v) < c(v) dan noemen we de lijn  f-onverzadigd.

Een nieuwe functie:   t(v)  geeft aan hoeveel de stroom door lijn v nog zou kunnen toenemen.  Dus:   t(v) = c(v) - f(v) 
Voor een f-verzadigde verbindingslijn is  t(v) = 0  (er is geen toename meer mogelijk).
Ook aan een hele route R kunnen we een t(R) toekennen:  dat is de kleinste t van alle verbindingslijnen waaruit R bestaat.  (eigenlijk staat daar zoiets als:  "Een route kan zoveel toenemen als zijn zwakste schakel").  Een route R heet nu f-onverzadigd  als  t(R) > 0.
Een route R van B0 naar P0  die f-onverzadigd is  noemen we een  f-vermeerderende route.

Je zult al wel begrijpen dat de stroom in een netwerk nog niet maximaal is zolang er nog zulke f-vermeerderende routes te vinden zijn. Immers daar is nog winst te halen want daar kan de stroom groter.
       
       
De rode route is een f-vermeerderende route want overal is  t(v) > 0. De kleinste t(v) die voorkomt is die van lijn T1T3, want daar is  t(v) = 1.  Daarom kunnen alle stromen met 1 verhoogd worden. Dat geeft de nieuwe stromen rechts met stroomwaarde 14.
Nou; dezelfde procedure dan nog maar een keer:
       
       
Alweer eentje hoger.
Nou, zo gaan we steeds maar door totdat er geen f-vermeerderende route te vinden is.

Kijk uit met verbindingen de andere kant op!

Daar bedoel ik het volgende mee. 
Stel dat je in het netwerk waar we gebleven waren de volgende route kiest:
       
       
Dan zit daar die rare route T2T1 in die "tegen de stroom ingaat". In zo'n geval kun je doen alsof de t(v) gelijk is aan  f(v)  want door de stroom f(v) nul te maken gaat er meer stroom de andere kant op;  dat zie je in de figuur:  als je T2T1 nul maakt dan kan  T1P1 eentje hoger worden!
Rechts zie je een verbetering:  stroomwaarde is nu al 16.
Voor de netheid moet je dus eigenlijk zeggen:
       

       
En de nieuwe stromen in route R  met kleinste waarde t(R) worden dan:
 

       
De stroom in bovenstaand netwerk kan nu niet beter. Dat kun je hiernaast zien:  in de getekende snede  (van blauwe B0-knopen naar paarse P0-knopen)  hebben alle verbindingen t = 0. Omdat elke route een lijn van deze snede moet passeren heeft elke route t(R) = 0

Je ziet dat de maximale stroomwaarde gelijk is aan de som van de stromen door deze snede (4 + 3 + 4 + 5 = 16)


 
Een algoritme
(naar  Ford & Fulkerson, 1957)

Tot nu toe was het nog "een beetje proberen" om zulke f-vermeerderende routes te vinden. Maar ook daar bestaat gelukkig een algoritme voor.
Wat we gaan doen is het volgende:  We beginnen bij B0 en gaan vanaf daar een boom maken. Maar dat doen we door alleen maar f-onverzadigde verbindingslijnen te gebruiken. Zo'n boom heet dan ook een f-onverzadigde boom.
Dat langzaamaan maken/uitbreiden van de f-onverzadigde boom kan op twee manieren gebeuren  ("met de stroom mee"" en ""tegen de stroom in"):
       

1.

Voeg een f-onverzadigde verbinding toe die loopt van een (knooppunt-van-de-huidige-boom) naar een (knooppunt-nog-niet-van-de-boom).

2.

Voeg een verbindingslijn toe die van een (knooppunt-niet-van-de-huidige-boom) naar een (knooppunt-van-de-boom) loopt en die positieve
f
-waarde heeft (dus niet nul).
       
En nou gaat het er maar om of die boom punt  P0 gaat bereiken. Als dat zo is, dan hebben we een nieuwe f-vermeerderende route gevonden. Na verbeteren van de stroomfunctie beginnen we gewoon weer opnieuw.
Als we P0 niet kunnen bereiken met onze boom, dan was onze f optimaal.

Blijft nog over de vraag:   "Als je meerdere verbindingslijnen aan de boom zou kunnen toevoegen, welke moet je dan nemen?"
Die vraag beantwoorden we door de knooppunten van de boom te nummeren.
Begin met knooppunt B0  nummer 1 te geven, en elk nieuw aan de boom toegevoegde knooppunt krijgt een volgend nummer.
Het uitbreiden van de boom gaat nu volgens de regel:
       

Je mag een knooppunt van de boom pas onderzoeken op mogelijke uitbreidingen,
als je alle eerder genummerde knooppunten al hebt geprobeerd.

       
Deze kleine uitbreiding komt van  Edmonds en Karp (1970)

Hier is een heel eenvoudig voorbeeld van wat er anders mis kan gaan:

Neem het super-simpele netwerkje hiernaast.
Je ziet natuurlijk meteen dat de maximale stroomwaarden gelijk is aan 28, maar laten we ons algoritme van het maken van een boom eens gebruiken. Dat doen we eerst zonder die extra voorwaarde.

Begin met overal stroom 0, en ga een boom maken:

Eerste boom (de keuzes zijn "willekeurig")
Begin bij B0.
Kies dan B0B1 als eerst tak  (t = ∞).
Kies dan  B1T2 als tweede tak (t = 14)
Kies dan  T2T1 als derde tak (t = 2)
Kies dan  T1P1 als vierde tak  (t = 14)
Dat geeft een f-vermeerderende route met t waarde 2 (de laagste t van de gevonden takken) , dus kunnen we alle stromen in die route 2 verhogen en opnieuw beginnen.

Tweede boom (de keuzes zijn "willekeurig"):
Begin bij B0.
Kies dan B0B1 als eerst tak  (t = ∞).
Kies dan  B1T1 als tweede tak (t = 14)
Kies dan  T2T1 als derde tak (t = 2, want f = 2 en deze is andersom)
Kies dan  T1P1 als vierde tak  (t = 14)
Dat geeft een f-vermeerderende route met t waarde 2, dus kunnen we alle stromen in die route 2 verhogen (en T2T1 nul maken) en opnieuw beginnen.

Zie je al wat er gebeurt?

Het zou kunnen dat we om-en-om de routes B0B1T2T1P1P0 en  B0B1T1T2P1P0  kiezen, en elke keer de stroomwaarde met 2 verhogen. Natuurlijk is dat niet een handige keuze, maar zonder voorwaarden aan de manier waarop we de boom uitbreiden zou dit kunnen gebeuren (vooral bij erg grote netwerken waar alles lang niet zo overzichtelijk is als hier).

Maar met onze handige extra voorwaarde kan dat niet meer. Kijk maar:

Handige boom (kies laagste knoopnummer):
Kies B0  (knoop nr. 1)
Kies B0B1 als eerste tak  (t = ∞,  B1 = knoop nr. 2)

Kies B1T2 als tweede tak  (t = 14, T2 = knoop  nr. 3): je mag alleen vanaf B1 uitbreiden omdat B0 niet verder wil!!!
Nu mag je niet T2T1 kiezen want die loopt vanaf T2, en T2 (nr. 3) is later genummerd dan B(nr. 2), dus je moet eerst proberen of je vanaf B1 nog kunt uitbreiden.
Dat geeft automatisch keuze B1T1 als derde tak  (t = 14,  T1  = knoop nr. 4)
B1 wil nu niet verder, dus nu moet je eerst vanaf T2 proberen!  (laagste voorradige nummer)
Dat geeft T2P1 als tak 4 en daarna de f-vermeerderende route  B0B1T2P1P0  met t = 14.

Bij de tweede boom vind je dan de route onderlangs voor nog eens t = 14, en dan heb je de maximale stroomwaarde 28 gevonden.

Uitgebreid slotvoorbeeld.

       
Bedenk in het volgende voorbeeld goed:

BLAUW = knooppuntnummer
,
ROOD = capaciteit
,  
GROEN = huidige stroom.
       

       

h.hofstede (h.hofstede@hogeland.nl)