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

Netwerken.
       
Een Netwerk is een speciaal soort gerichte graaf (Digraaf). Een netwerk (vanaf nu aangegeven met N) heeft een onderliggende digraaf  D, maar daar is nog iets extras mee aan de hand.
De knooppunten van een netwerk N worden onderscheiden in 3 soorten:
Bronnen  (verzameling B)
Tussenliggende punten  (verzameling T)

Putten (verzameling P)
Verder is er een functie c die aan elke verbindingslijn een getal toekent, dat we de capaciteit van die verbindingslijn noemen.
       
Vergelijk de situatie maar met een economisch model:  de Bronnen zouden de fabrieken kunnen voorstellen, de Putten zouden dan de afzetmarkten kunnen zijn, en de verbindingslijnen zijn transportwegen waarbij de capaciteit zegt hoeveel goederen er langs elke weg vervoerd kunnen worden.
Of je kunt het ook letterlijk nemen:  de bronnen maken afvalwater, de putten zijn de plaatsen waar dat geloosd moet worden, en de verbindingslijnen zijn waterleidingen, elk met een eigen capaciteit (doorsnede).
 
Hiernaast zie je een netwerk met 2 bronnen en 3 putten en 4 tussenliggende punten.

Merk nog even op:
- Bronnen hebben alleen uitgaande verbindingslijnen.
- Putten hebben alleen inkomende verbindingslijnen.
- Alle capaciteiten zijn positief.

opmerking:  Als de verbindingslijnen beide kanten op kunnen vervoeren (zoals waterleidingen), dan kun je dat makkelijk tot stand brengen door tussen die punten twee gerichte verbindingslijnen te tekenen met dezelfde capaciteit;  eentje heen en eentje terug. 
Een stroom in een netwerk is nu een functie die aan elke verbindingslijn een waarde toekent  (de groene getallen in de figuur hieronder), waarbij wordt voldaan aan twee voorwaarden:
     
1. De toegekende waarden zijn allemaal hoogstens gelijk aan de capaciteit van de lijnen.
2. Voor tussenliggende knopen geldt:  totale stroom erin  = totale stroom eruit.  Dat zorgt er meteen voor dat de totale stroom uit B gelijk is aan de totale stroom in P, immers als voor elk T-knooppunt apart geldt
"in = uit", dan geldt dat ook voor de som van alle T-knooppunten samen.
     
De totale stroom uit-B en in-P (die zijn dus gelijk)  noemen we wel de stroomwaarde van het netwerk (in dit voorbeeld is de stroomwaarde 13). Meestal (nou ja, eigenlijk altijd) zullen we op zoek gaan naar de maximale stroomwaarde van een netwerk.
       
Vaak is het handig om een netwerk om te bouwen tot een ander netwerk met slechts n Bron en n Put.  Dat kan heel eenvoudig:  leg vr alle bronnen n nieuw Bronpunt (B0) en geef dat punt verbindingslijnen met capaciteit naar alle B-knopen. Leg ook na alle putten een nieuw Putpunt (P0) en geef alle P-knopen een verbindingslijn met capaciteit  naar dat nieuwe punt. Dat zou er in ons voorbeeld z uitzien:
       

       
Snedes.
       
Je maakt als volgt een snede in een netwerk:
Verdeel de knooppunten in twee groepen:  eentje (de B0-groep) met B0 erin en eentje (de P0-groep) met P0 erin.
Een snede bestaat nu uit alle verbindingslijnen die van de B0-groep naar de P0-groep lopen.
       

       
Hier zie je een B0-groep (blauw) en een P0-groep (paars). De rode verbindingslijnen samen vormen een snede. De capaciteit van deze snede is de som van de stromen van de verbindingslijnen. De hier gemaakte snede heeft capaciteit 20. Bedenk goed dat je alleen lijnen VAN de B0-groep NAAR de P0-groep moet nemen. Als de verbindingslijn tussen T3 en T4 in het bovenstaande voorbeeld de andere kant op had gelopen, dan hoorde hij niet bij de snede!

Stelling.

De stroomwaarde van een netwerk is kleiner of gelijk aan de capaciteit van een snede.

   
Bewijs:
  1.  Stromen van B0-groep naar P0-groep    Capaciteit snede  (meer kan er nou eenmaal niet door).
2.  Stroomwaarde  ≤  Stromen van B0-groep naar P0-groep
   
 

  Kijk maar naar dit stripverhaal.
We beginnen met B0 en gaan de verzameling B0-knooppunten langzaam uitbreiden.  B0 heeft som van uitgaande stromen 13 en dat is precies gelijk aan de stroomwaarde.
Voeg B1 toe, en vervang de ingaande stromen naar B1 door de uitgaande. Dan blijft de som van de uitgaande stromen uit onze verzameling gelijk aan de stroomwaarde. Nog steeds verlaten 6 en 7 onze grijze verzameling.
Voeg op dezelfde manier B2 toe en vervang de ingaande 7 door de uitgaande 3 en 4.  Blijft 13.....
Voeg dan T1 toe.
Ga net zolang door tot je alle B0-groep knopen hebt gehad.
Dan is de som van de rode uitgaande pijlen hoogstens gelijk aan de stroomwaarde. Het zou immers kunnen dat er pijlen van de P0-groep naar de B0-groep gaan, en die tellen niet mee voor de snede.  Dat zou zo bijvoorbeeld zo zijn als je T1 ook paars zou maken  (dus bij de P0-groep zou zetten). Kijk maar naar deze snede:
   
 

   
  Nu zijn de uitgaande stromen uit onze grijze verzameling ineens 14 geworden omdat die verbinding van T1 naar T2 niet meetelt. Je ziet dat de snede nu ook 14 is.
   
  uit 1. en  2. volgt direct de stelling.
     
       
Waarschijnlijk is het intutief nog beter te begrijpen wat er aan de hand is als je bedenkt dat de verzamelingen B0-knopen en P0-knopen met elkaar verbonden zijn door een aantal (minstens n) verbindingslijnen. Zie de figuur linksonder.
       

       
Een snede bestaat uit alle verbindingen van links naar rechts tussen beide verzamelingen. Omdat alle stroom uiteindelijk van B0 naar P0 moet, moet dus alle stroom deze snede passeren. Dus kan de totale stroom nooit groter zijn dan de capaciteit van de snede. De snede met minimale capaciteit is zoiets als de "smalste doorsnede"  van het netwerk.
       
Belangrijk gevolg:

maximale stroomwaarde    minimale capaciteit snede

       
Vanwege de stelling hierboven geeft de snede met de kleinste capaciteit een bovengrens voor de stroomwaarde.
       
Hier zie je, om er een beetje aan te wennen, een aantal snedes van bovenstaand netwerk. De B0-groep is steeds aangegeven, en de som van de uitgaande rode lijnen bepaalt de grootte van de snede.
       

       
Let nog even op die snede van 17:  de ingaande lijn met capaciteit 3 telt niet mee!

Nou zou je om de maximale stroomwaarde te bepalen natuurlijk alle mogelijke snedes kunnen tekenen en dan degene met de kleinste totale som kunnen nemen. Maar dat is nogal een werk:  je moet van een verzameling van n knooppunten (B0 en P0 niet meegerekend) een willekeurige deelverzameling kiezen.  Dat kan op 2n  manieren!!!!

In de volgende les zullen we een snellere manier bekijken om de maximale stroomwaarde te vinden.  Je bent vast al nieuwsgierig.....
       

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