Page 15 - Grafentheorie HS 6 Bomen

HS 6 Bomen

5. Hoe groot is het chromatisch getal van een boom?
6. Welke van de onderstaande grafen is een boom?

7. Hieronder worden twee opspannende bomen van dezelfde graaf gegeven.
Welke opspannende boom is een minimaal opspannende boom?

8. Er liggen zeven beverburchten in een vijver niet ver van de oever. Tussen de burchten kunnen de
bevers bruggen bouwen zoals door de stippellijnen is aangegeven. De getallen bij de lijnen geven
aan hoeveel bomen je nodig hebt voor elke brug. De bevers willen genoeg bruggen bouwen zodat
elke burcht vanop de oever kan bereikt worden zonder te zwemmen.

t
e
n
.
o
l
e
h
t
a
m
UGent.be
.
w
w
Bepaal het kleinste aantal bomen dat hiervoor nodig is. w

Controleer met het algoritme van Prim en ook Kruskal.

© 2021 Ivan De Winne ivan@mathelo.net 14