Page 16 - Grafentheorie HS 6 Bomen

HS 6 Bomen

9. Wat is het verband tussen aantal knopen van een (samenhangende gewogen) graaf N en het aantal
bogen van de minimaal opspannende boog van deze graaf?

10. Beschouw onderstaande gewogen samenhangende graaf waarbij de afstanden (gewichten) van de
bogen allemaal verschillend zijn.

Hoeveel minimaal opspannende bomen kunnen er in dit geval gevonden worden?

Controleer dit met het algoritme van Prim en ook het algoritme van Kruskal.

11. Bepaal met de methode van Kruskal de minimaal opspannende boom van de volgende graaf.

t
e
n
.
o
l
e

h
t
a
12. Gebruik het algoritme van Prim voor het berekenen van de minimaal opspannende boom van de m
vorige graaf. Is het resultaat hetzelfde? .
w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 15