Voorbeeld Kruskal

Report
Minimum Spanning Tree
Wat is MST?
• Minimum spanning tree
• De meest efficiënte manier vinden om een verbonden
netwerk op te bouwen
Wat is een tree/boom?
• Graaf :
– een verzameling knopen (vertices): 
– een verzameling kanten (edges):  ⊆  × 
• Een boom is een graaf  waarin er één uniek simpel pad is
tussen elk paar knopen
• Een boom is verbonden (connected): je kunt vanuit iedere
knoop in iedere andere knoop komen
• Een boom bevat geen cykels: je kan niet in een rondje
lopen
Hoeveel kanten heeft een boom?
• Een boom op  knopen heeft  − 1 kanten
• Basisgeval: triviale boom met 1 knoop heeft 0 kanten
• Inductiestap: stel iedere boom met  <  knopen heeft 
− 1 kanten. Voor een boom met  knopen geldt dan dat…
 knopen
 − 1 kanten
 −  knopen
 −  − 1 kanten
Hoeveel kanten heeft een boom?
• Een boom op  knopen heeft  − 1 kanten
• Basisgeval: triviale boom met 1 knoop heeft 0 kanten
• Inductiestap: stel iedere boom met  <  knopen heeft 
− 1 kanten. Voor een boom met  knopen geldt dan dat…
…hij bestaat uit een kant die twee losse bomen verbindt, één
met  knopen, de ander met  −  knopen. Met de IH hebben
ze  − 1 en  −  − 1 knopen.
De boom heeft dus  − 1 +  −  − 1 + 1 =  − 1 knopen 
 knopen
 − 1 kanten
 −  knopen
 −  − 1 kanten
Definitie MST
• “Bepaal de boom met het minste aantal kanten” is dus niet
zo spannend…
• Gewogen graaf:  = ,  samen met een wegingsfunctie
:  → ℝ kent aan iedere kant een gewicht toe (“lengte”)
• Minimum spanning tree  van een verbonden, gewogen
graaf  = ,  is een deelverzameling  ⊆  zodat (, ) een
boom is en ∈ () minimaal is
Voorbeeld MST
Gewicht: 35
MST als optimaliseringsprobleem
• Invoer: verbonden, gewogen graaf (, , )
• Zoekruimte: alle deelverzamelingen van : ()
• Toelaatbaarheid: het moet een boom zijn
• Doelfunctie:   =
∈ ()
Bomen bouwen 1
• Je kunt een bestaande boom aanpassen:
– Voeg een kant toe → cykel dus geen boom meer
– Haal een kant van de cykel weg → het is weer een boom
Bomen bouwen 2
• Iedere verbonden graaf (, ) heeft een deelverzameling 
⊆  zodat (, ) een boom is
• Als (, ) verbonden maar geen boom is dan bevat (, )
een cykel
• Gooi willekeurig een kant van die cykel weg
• Is het resultaat een nog geen boom? Herhaal!
• Gevolg: graaf  verbonden en  − 1 kanten →  is boom
Als  geen boom zou zijn zou er een deelverzameling zijn
van minder dan  − 1 kanten die een boom zou zijn ↯
Hoe bepaal je een MST?
• Algoritmische trukendoos:
– Divide & Conquer
• Verdeel de graaf in twee deelgraven?
• Verbind de deel-MST’s met de lichtste kant?
• Fail…
– Dynamisch Programmeren
Hoe bepaal je een MST?
• Algoritmische trukendoos:
– Divide & Conquer
• Verdeel de graaf in twee deelgraven?
• Verbind de deel-MST’s met de lichtste kant?
• Fail…
– Dynamisch Programmeren
• Optimal Substructure: een optimale oplossing bevat
een optimale deeloplossing
• Een MST bestaat uit 2 MST’s verbonden door 1 edge
Hoe bepaal je een MST?
• DP heeft naast OSS ook overlapping subproblems nodig
• Het kan wél, maar…
• Het probleem heeft een greedy choice property!
Algoritme van Prim
• Bouw de boom op door steeds 1 kant toe te voegen
• Kies een beginknoop
• Bekijk de knopen die je in 1 stap kunt bereiken
• Kies de lichtste van de uitgaande kant
• Je kiest steeds de lichtste boomverlatende kant
Algoritme van Prim
Algoritme van Prim
Algoritme van Prim
Algoritme van Prim
Algoritme van Prim
Algoritme van Prim
Algoritme van Prim
Algoritme van Prim
Algoritme van Prim
Implementatie van Prim
• Hoe kun je snel de lichtste kant vinden? Priority Queue!
• Representatie van het resultaat? Parent Pointers
Pseudocode van Prim
foreach(Vertex v in graph.Vertices) v.Key = ∞;
root.Key = 0;
PQ = new PriorityQueue(graph.Vertices);
while(!PQ.Empty)
u = PQ.ExtractMin();
foreach(Vertex v in u.Neighbors)
if(PQ.Contains(v) && w(u,v) < v.Key)
v.Parent = u;
PQ.DecreaseKey(v, w(u,v));
Algoritme van Prim
Priority Queue
B: 4
H: 8
Algoritme van Prim
Priority Queue
B: 4
C: 8
H: 8
Algoritme van Prim
Priority Queue
C: 8
I: 2
F: 4
D: 7
H: 8
Algoritme van Prim
Priority Queue
I: 2
F: 4
G: 6
D: 7
H: 8 H: 7
Algoritme van Prim
Pseudocode van Prim
foreach(Vertex v in graph.Vertices) v.Key = ∞;
root.Key = 0;
PQ = new PriorityQueue(graph.Vertices);
O(n)
while(!PQ.Empty)
u = PQ.ExtractMin();
foreach(Vertex v in u.Neighbors)
if(PQ.Contains(v) && w(u,v) < v.Key)
v.Parent = u;
PQ.DecreaseKey(v, w(u,v));
O(n)
O(log n)
totaal O(m)
O(log n)
Looptijd is dus   log  . Het kan nog sneller in ( +  log )
met een Fibbonacciheap – die doet decreasekey in (1) .
Pseudocode van Prim Dijkstra
foreach(Vertex v in graph.Vertices) v.Key = ∞;
root.Key = 0;
PQ = new PriorityQueue(graph.Vertices);
O(n)
while(!PQ.Empty)
u = PQ.ExtractMin();
foreach(Vertex v in u.Neighbors)
if(PQ.Contains(v) && w(u,v) + u.Key <
v.Parent = u;
PQ.DecreaseKey(v, w(u,v) + u.Key);
O(n)
O(log n)
totaal O(m)
v.Key)
O(log n)
Looptijd is dus   log  . Het kan nog sneller in ( +  log )
met een Fibbonacciheap – die doet decreasekey in (1) .
Bewijs van Prim
• We moeten de GCP bewijzen
• GCP: Zij  een MST van (, ) en stel dat  ⊆ . Als  een
lichtste kant is die een knoop in  met een knoop niet in 
verbindt ( is -verlatend), dan is  ∪ {} deelverzameling
van een MST ′.
•
•
•
•
Als  ∈  dan is het goed. Stel dus dat  ∉ .
Dan bevat  ∪ {} een cykel. Bekijk de kanten van die cykel.
De cykel bevat naast  nog een -verlatende kant .
  ≥ () dus T ′ =  ∪ \  is een minimale(re) spanning
tree (  ′ =   +   −   ≤ ())
Algoritme van Kruskal
• Prim: laat één boom steeds verder groeien
• Kruskal: werkt met een woud met allemaal losse stukjes
boom
• Iedere verbonden graaf heeft een deelgraaf die boom is:
– Herhaald kanten van cykels weglaten
• Kan ook andersom: maak een boom door steeds toe te
voegen:
A = ∅;
foreach(Edge e in graph)
if(A ∪ e bevat geen cykel)
A = A ∪ {e};
• Het resultaat hangt af van de volgorde!
Algoritme van Kruskal
• Bekijk de kanten van licht naar zwaar
• Voeg steeds de kant toe als hij geen cykel introduceert
• Cykels testen: Union-Find!
Sort(edges);
foreach(Vertex v) MakeSet(v);
foreach(Edge e)
if(FindRep(e.A) ≠ FindRep(e.B))
resultaat.Add(e);
Union(e.A, e.B);
Algoritme van Kruskal
• Bekijk de kanten van licht naar zwaar
• Voeg steeds de kant toe als hij geen cykel introduceert
• Cykels testen: Union-Find!
Sort(edges);
foreach(Vertex v) MakeSet(v);
foreach(Edge e)
if(FindRep(e.A) ≠ FindRep(e.B))
resultaat.Add(e);
Union(e.A, e.B);
Sort is   log  . () union find-operaties kosten     .
Sorteren domineert. Totaal:   log  = ( log )
Voorbeeld Kruskal
HG
IC
GF
AB
CF
IG
CD
HI
AH
BC
DE
FE
Voorbeeld Kruskal
HG: A B C D E F GH I
IC
GF
AB
CF
IG
CD
HI
AH
BC
DE
FE
Voorbeeld Kruskal
HG: A B C D E F GH I
IC: A B CI D E F GH
GF
AB
CF
IG
CD
HI
AH
BC
DE
FE
Voorbeeld Kruskal
HG: A B C D E F GH I
IC: A B CI D E F GH
GF: A B CI D E FGH
AB
CF
IG
CD
HI
AH
BC
DE
FE
Voorbeeld Kruskal
HG:
IC:
GF:
AB:
CF
IG
CD
HI
AH
BC
DE
FE
A B C D E F GH I
A B CI D E F GH
A B CI D E FGH
AB CI D E FGH
Voorbeeld Kruskal
HG:
IC:
GF:
AB:
CF:
IG
CD
HI
AH
BC
DE
FE
A B C D E F GH I
A B CI D E F GH
A B CI D E FGH
AB CI D E FGH
AB CFGHI D E
Voorbeeld Kruskal
HG:
IC:
GF:
AB:
CF:
IG:
CD
HI
AH
BC
DE
FE
A B C D E F GH I
A B CI D E F GH
A B CI D E FGH
AB CI D E FGH
AB CFGHI D E
niks
Voorbeeld Kruskal
HG:
IC:
GF:
AB:
CF:
IG:
CD:
HI
AH
BC
DE
FE
A B C D E F GH I
A B CI D E F GH
A B CI D E FGH
AB CI D E FGH
AB CFGHI D E
niks
AB CDFGHI E
Voorbeeld Kruskal
HG:
IC:
GF:
AB:
CF:
IG:
CD:
HI:
AH
BC
DE
FE
A B C D E F GH I
A B CI D E F GH
A B CI D E FGH
AB CI D E FGH
AB CFGHI D E
niks
AB CDFGHI E
niks
Voorbeeld Kruskal
HG:
IC:
GF:
AB:
CF:
IG:
CD:
HI:
AH:
BC
DE
FE
A B C D E F GH I
A B CI D E F GH
A B CI D E FGH
AB CI D E FGH
AB CFGHI D E
niks
AB CDFGHI E
niks
ABCDFGHI E
Voorbeeld Kruskal
HG:
IC:
GF:
AB:
CF:
IG:
CD:
HI:
AH:
BC:
DE
FE
A B C D E F GH I
A B CI D E F GH
A B CI D E FGH
AB CI D E FGH
AB CFGHI D E
niks
AB CDFGHI E
niks
ABCDFGHI E
niks
Voorbeeld Kruskal
HG:
IC:
GF:
AB:
CF:
IG:
CD:
HI:
AH:
BC:
DE:
FE
A B C D E F GH I
A B CI D E F GH
A B CI D E FGH
AB CI D E FGH
AB CFGHI D E
niks
AB CDFGHI E
niks
ABCDFGHI E
niks
ABCDEFGHI
Voorbeeld Kruskal
HG:
IC:
GF:
AB:
CF:
IG:
CD:
HI:
AH:
BC:
DE:
FE:
A B C D E F GH I
A B CI D E F GH
A B CI D E FGH
AB CI D E FGH
AB CFGHI D E
niks
AB CDFGHI E
niks
ABCDFGHI E
niks
ABCDEFGHI
niks
Correctheid van Kruskal
• Lemma: gegeven MST  van graaf (, ). Stel dat  ⊆ .
Zij  ∈  een lichtste kant zodat  ∪ {} cykelvrij is (en 
∉ ). Dan bestaat er MST ′ zodat  ⊆ ′ en  ∈ ′.
Bovendien geldt dat T ′ ⊆  ∪  .
• Bewijs:
– Als  ∈  neem  ′ = 
– Als  ∉  bevat  ∪ {} een cykel
–  ∪ {} is cykelvrij dus de cykel bevat kant  ∉ ,  ≠ 
–  ∪ {} is cykelvrij:  ∪  ⊆  en  is een boom
–  is een lichtste kant met die eigenschap dus   ≤ ()
– Dus T ′ =  ∪ \  ⊆  ∪  is een minimale(re) MST
want   ′ =   +   −   ≤ ().
Correctheid van Kruskal
• Het lemma is niet genoeg. Bewijs met invariant (soort inductie)
initialisatie:  = {1, 2, … , }, 0 = ∅
for(i = 1 to n)
invariant:  is uit te breiden met  t/m  tot MST
if( voegt geen cykel toe)
+1 =  ∪ 
else
+1 = 
Wil: invariant is nu waar voor  + 1
• In het begin is de invariant waar ( is een verbonden graaf)
Correctheid van Kruskal
for(i = 1 to n)
invariant:  is uit te breiden met  t/m  tot MST
if( voegt geen cykel toe)
+1 =  ∪ 
else
+1 = 
Formeel “er is MST  zodat  ⊆  ⊆  ∪ { , …  }”
• Stel de invariant is waar voor zekere 
• Dan is er een MST  zodat  ⊆  ⊆  ∪ { , …  }
Correctheid van Kruskal
for(i = 1 to n)
invariant:  is uit te breiden met  t/m  tot MST
if( voegt geen cykel toe)
+1 =  ∪ 
else
+1 = 
Formeel “er is MST  zodat  ⊆  ⊆  ∪ { , …  }”
• Stel de invariant is waar voor zekere 
• Dan is er een MST  zodat  ⊆  ⊆  ∪ { , …  }
– Als het if-statement false is ( ∪  bevat een cykel):
• +1 ⊆  is zeker waar want  = +1
•  ⊆ +1 ∪ {+1 , …  } geldt ook want  kan geen element
van  zijn,  is cykelvrij en bevat  en  ∪  is niet
cykelvrij
Correctheid van Kruskal
for(i = 1 to n)
invariant:  is uit te breiden met  t/m  tot MST
if( voegt geen cykel toe)
+1 =  ∪ 
else
+1 = 
Formeel “er is MST  zodat  ⊆  ⊆  ∪ { , …  }”
• Stel de invariant is waar voor zekere 
• Dan is er een MST  zodat  ⊆  ⊆  ∪ { , …  }
– Als het if-statement true is ( ∪  is cykelvrij) roepen we
het lemma in. Er is een MST ′ met  ∪  ⊆  ′ ⊆  ∪  .
Lemma: gegeven MST  van graaf
(, ). Stel dat  ⊆ . Zij  ∈ 
een lichtste kant zodat  ∪ {}
cykelvrij is (en  ∉ ). Dan bestaat
er MST ′ zodat  ⊆ ′ en  ∈ ′.
Bovendien geldt dat T ′ ⊆  ∪  .
Correctheid van Kruskal
for(i = 1 to n)
invariant:  is uit te breiden met  t/m  tot MST
if( voegt geen cykel toe)
+1 =  ∪ 
else
+1 = 
Formeel “er is MST  zodat  ⊆  ⊆  ∪ { , …  }”
• Stel de invariant is waar voor zekere 
• Dan is er een MST  zodat  ⊆  ⊆  ∪ { , …  }
– Als het if-statement true is ( ∪  is cykelvrij) roepen we
het lemma in. Er is een MST ′ met  ∪  ⊆  ′ ⊆  ∪  .
– +1 =  ∪  ⊆  ′ dus we hoeven enkel te checken dat  ′
⊆ +1 ∪ {+1 , …  }
– Dat kan:  ′ ⊆  ∪  ⊆  ∪  , …  =  ∪  ∪ +1 , … 
= +1 ∪ {+1 , …  } 
Correctheid van Kruskal
initialisatie:  = {1, 2, … , }, 0 = ∅
for(i = 1 to n)
invariant:  is uit te breiden met  t/m  tot MST
if( voegt geen cykel toe)
+1 =  ∪ 
else
+1 = 
bewezen: invariant is nog steeds waar (na ophogen i)
Zodra de for-loop klaar is dan “is +1 met en+1 t/m en uit te
breiden tot MST” dus is +1 een MST.
Is de MST uniek?
• Nee, maar wel als de kantgewichten uniek zijn!
Stel  = (, , ) is een ongerichte gewogen graaf en  is
injectief (verschillende kanten naar verschillende waarden).
Stel we hebben ,  ⊆  MST’s van  en ze zijn niet hetzelfde.
Dan zijn er kanten die in precies 1 van ,  zitten.
Bekijk de laagste kant  die niet in beide zit.
Stel z.v.a. dat  ∈ . Dan bevat  ∪ {} een cykel.
 ∈  en  bevat géén cykel dus ≥ 1 cykelkant  zit alleen in .
Is de MST uniek?
• Nee, maar wel als de kantgewichten uniek zijn!
Stel  = (, , ) is een ongerichte gewogen graaf en  is
injectief (verschillende kanten naar verschillende waarden).
Stel we hebben ,  ⊆  MST’s van  en ze zijn niet hetzelfde.
Dan zijn er kanten die in precies 1 van ,  zitten.
Bekijk de laagste kant  die niet in beide zit.
Stel z.v.a. dat  ∈ . Dan bevat  ∪ {} een cykel.
 ∈  en  bevat géén cykel dus ≥ 1 cykelkant  zit alleen in .
Per constructie   > () dus  ∪ \  is een MST met
lager gewicht dan . Tegenspraak!  en  zijn hetzelfde.
Kroegentocht of TSP
• Travelling Salesman
• Bepaal een volgorde (rondtocht) om zo snel mogelijk een
aantal knopen te bezoeken in een graaf.
• Handelsreiziger: wil zijn product in een aantal steden
verkopen, wat is de kortste route.
• Is een “moeilijk” probleem: NP-compleet
• Waarschijnlijk kost het exponentiële tijd om op te lossen
TSP-Approximatie
• Met behulp van MST kunnen we TSP benaderen
TSP-Approximatie
• Met behulp van MST kunnen we TSP benaderen
• TSP is hoogstens 2 × zo lang als MST
TSP-Approximatie
• Met behulp van MST kunnen we TSP benaderen
• TSP is hoogstens 2 × zo lang als MST
•
•
•
•
Maar ook: MST is hoogstens zo groot als TSP
Laat kanten weg uit TSP tot je een MST hebt
Ergo: MST ≤ TSP ≤ 2 MST
MST 2 −approximeert TSP
• Werkt alleen als symmetrisch 
• Approximatie (begrensd) vs. heuristiek
Prim VS Kruskal
• Prim: breidt 1 boom steeds verder uit (als Dijkstra)
• Kruskal: laat boom groeien uit meerdere stukjes
Prim
Kruskal
Datastructuur
Priority Queue
Union-Find
Looptijd
( log ) of ( +  log ) ( log ) (sorteren)
Extra ruimte
()
()
• Ik vind Kruskal beter: makkelijk te implementeren en vaak
betere constante in de grote 
• Het is een kwestie van smaak
Conclusie
• Minimum Spanning Tree: lichtste, verbonden deelgraaf
• Algoritme van Prim of Kruskal
• Je kan van alles bewijzen als je een kant toevoegt en de
cykel weer doorbreekt
• Lokale eigenschappen → greedy algoritme
• Toepassingen van MST:
– Lege collegezaal (LAN-party!)
– Netwerk-broadcast
– Handschriftherkenning
– TSP-approximatie (kroegentocht)

similar documents