Page 9 - Grafentheorie HS 6 Bomen

HS 6 Bomen

Vervolgens zijn er nog twee bogen met gewicht 2 die kunnen worden toegevoegd.
Hou er alleen rekening mee dat er geen cykels (kringen) ontstaan.

Voeg tenslotte één van de twee bogen met gewicht 3 toe.

of ook

In beide gevallen is het gewicht van deze minimale opspannende boom van de graaf gelijk aan 10.

t
e
n
.
o
l
Opmerking: Wat is het verschil tussen het algoritme van Kruskal en Prim? e
h
t
• Het algoritme van Prim start met een knoop a
m
• Het algoritme van Kruskal start met een boog. .
w
• Bij het algoritme van Prim moeten de toegevoegde knopen en bogen met elkaar verbonden zijn.
w
• Bij het algoritme van Kruskal moeten de toegevoegde takken niet noodzakelijk met elkaar w
verbonden zijn.

© 2021 Ivan De Winne ivan@mathelo.net 8