grafentheorie verbindingsprobleem

© 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 {V₁, V₂, ..., V_n-1}

Stel dat B^* niet optimaal is.......

Dan is er in de lijst van wél 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 B₁.Dus dat is degene waar in het rijtje {V₁, V₂, ...} zo laat mogelijk een afwijkende V voorkomt vergeleken met B*.
Noem deze eerste afwijkende zijde V_i (we kiezen dus de optimale boom B₁ met maximale i).

B₁ + V_i 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 V_i kan met de eerdere V's geen cykel maken want B₁ heeft geen cykel.
Neem zo'n latere V_j uit de cykel en laat die weg uit de graaf B₁.
Dan heb je een nieuwe graaf B₂ gekregen die óók een opspannende boom is.
gewicht van B₂ = gewicht van B₁ + gewicht van V_i - gewicht van V_j
maar omdat j een latere verbinding is dan i is het gewicht van j ≥ gewicht van i
dus dan is gewicht van B₂ ≤ gewicht van B₁
B₂ is dan óók een optimale boom, met als eerste afwijkende verbindingslijn V_j groter dan V_i
Dat is in tegenspraak met het feit dat B₁ de zo laat mogelijk afwijkende V_i 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 B₁ en B^* pas bij de 4^e keus voor het eerst verschillen (V₄) , en dat daarvoor in de plaats in B₁ werd gekozen voor de blauwe verbinding (4).
Dan heeft B₁+ V₄ een cykel, in dit geval (4)(8)(1)(7)
Als je uit B₁ + V₄ van die cykel nu bijv. V_j = (8) weglaat krijg je B₂.
B₂ is ook een opspannende boom, met waarde ≤ B₁ dus ook een optimale boom (want (8) was groter dan (4) omdat je bij Kruskal altijd de kleinste eerst koos)
Maar B₂ is pas later dan V₄ongelijk aan B* en dat klopt niet met de aanname dat die V₄ 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

Bepaal van de volgende gewogen grafen een minimale opspannende boom, en geef het totale gewicht daarvan.

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.