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

Het verbindingsprobleem.
       
We gaan deze les een gewogen graaf bekijken waarvan we op jacht zijn naar de opspannende boom met het kleinste totale gewicht. Dat noemen we de minimale opspannende boom van deze graaf.  Denk bijvoorbeeld weer aan een stedennetwerk dat met spoorlijnen met elkaar verbonden moet worden. De gewichten stellen dan afstanden of kosten voor.

Eerst bekijken we een manier om een opspannende boom te maken als er geen gewichten zijn (of als alle gewichten gelijk zijn). Dat gaat heel eenvoudig: 
  Kies n voor n de zijdes en zorg er daarbij voor dat de graaf steeds acyclisch blijft.
  Stop als dat niet meer lukt.

Hier zie je een voorbeeldje:
       

       
Merk nog even op dat de graaf tussendoor helemaal niet samenhangend hoeft te blijven. Aan het eind komt vanzelf alles aan elkaar.
       
Kruskal's Algoritme
       
Kruskal breidde dit eenvoudige systeem uit om een minimale opspannende boom te vinden.  Dat deed hij met de belachelijk eenvoudige extra regel:
"Als je kunt kiezen, kies dan steeds degene met het kleinste gewicht".
       
Zo kinderlijk eenvoudig! Je kunt bijna niet geloven dat dit algoritme pas in 1956 werd gepubliceerd!! Je ziet trouwens dat dit weer een voorbeeld is van een "greedy"" algoritme.
Hier zie je een voorbeeldje. Volg de blauwe pijlen.
       

       
De optimale boom heeft totaalgewicht 34 gekregen. Beter kan dus niet!

Waarom werkt dit eigenlijk?
Een bewijs uit het ongerijmde. 
Noem de boom die we met dit algoritme hebben gevonden B*, en stel dat de achtereenvolgens gekozen verbindingslijnen gelijk zijn aan de lijst  {V1, V2, ..., Vn-1}

Stel dat B* niet optimaal is.......
  Dan is er in de lijst van wl optimale bomen dus een boom B te vinden die beter is. Kies nu van alle optimale bomen  B degene die het langst gelijk is aan B*.  Noem die boom B1.
Dus dat is degene waar in het rijtje  {V1, V2, ...} zo laat mogelijk een afwijkende V voorkomt vergeleken met B*.
Noem deze eerste afwijkende zijde Vi  (we kiezen dus de optimale boom B1 met maximale i).

B1 + Vi  bevat dan een cykel.  (een V toevoegen aan een boom geeft altijd een cykel)

Maar in die cykel zitten ook nog hogere V's  immers Vi  kan met de eerdere V's geen cykel maken want B1 heeft geen cykel.
Neem zo'n latere Vj uit de cykel en laat die weg uit de graaf  B1.
Dan heb je een nieuwe graaf B2 gekregen die k een opspannende boom is.
gewicht van B2 = gewicht van B1 + gewicht van Vi - gewicht van Vj 
maar omdat j een latere verbinding is dan i  is het gewicht van j  ≥ gewicht van i
dus dan is gewicht van  B2  ≤  gewicht van B1
B2 is dan k een optimale boom, met als eerste afwijkende verbindingslijn Vj groter dan Vi
Dat is in tegenspraak met het feit dat B1 de zo laat mogelijk afwijkende Vi had (i was maximaal)
Dus de aanname dat B* niet optimaal is klopt niet!
     
Verward door al die B's en V's en  i 's en  j 's??
Hou dan dit plaatje in gedachten:

       
Bij de verbindingslijnen van B* staat tussen haakjes als hoeveelste ze gekozen zijn.

Stel dat B1 en B*  pas bij de 4e keus voor het eerst verschillen (V4) , en dat daarvoor in de plaats in B1 werd gekozen voor de blauwe verbinding (4).
Dan heeft B1 + V4  een cykel, in dit geval  (4)(8)(1)(7)
Als je uit  B1 + V4 van die cykel  nu bijv. Vj = (8) weglaat krijg je B2.
B2 is ook een opspannende boom, met waarde  ≤  B1 dus ook een optimale boom  (want  (8) was groter dan (4) omdat je bij Kruskal altijd de kleinste eerst koos)
Maar B2 is pas later dan V4  ongelijk aan B*  en dat klopt niet met de aanname dat die V4 de grootste was......
       
Het algoritme van Prim
       
Prim bedacht een ander, maar ook zeer eenvoudig, algoritme om een minimale opspannende boom te vinden.
Zijn methode gaat in drie stappen:
       
stap 1.  kies een willekeurige ongemarkeerde knoop van de graaf en markeer die
stap 2. bekijk alle buren van gemarkeerde knopen van de graaf
bepaal van al die buren de kortste afstand tot een gemarkeerde knoop
stap 3 markeer de buur met de kleinste minimale afstand
ga weer naar stap 1.
       
Laten we het toepassen op dezelfde graaf die we al met Kruskal behandelden.
Kies bijvoorbeeld knooppunt K, en markeer dat (rood)
Die heeft drie buren (oranje) met afstanden 5, 6, 2
Markeer dus de buur met afstand 2.

Hieronder zie je hoe het verhaal verder gaat. Weer via zo'n blauwe pijlen-route. Het wijst zichzelf wel, denk ik...

(de rode pijl geeft steeds het nieuw te markeren knooppunt aan; bij gelijke minimale afstanden is zomaar eentje daarvan gekozen)
       

       
En zoals je ziet wordt uiteindelijk  precies dezelfde minimale opspannende boom van 34 gevonden die we ook al via Kruskal vonden.
       
  OPGAVEN
       
1. Bepaal van de volgende gewogen grafen een minimale opspannende boom, en geef het totale gewicht daarvan.
       
  a.

     

44

  b.

     

48

   
2. Hieronder staan een aantal plaatsen in Oost-Nederland die direct met elkaar verbonden zijn. De afstanden staan bij de verbindingswegen.
Ontwerp een netwerk dat deze verbindingswegen gebruikt, en dat al deze plaatsen met elkaar verbindt en waarvoor de totale lengte van alle verbindingen minimaal is.
       

       
     
       

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