Page 7 - Grafentheorie HS 6 Bomen
P. 7
HS 6 Bomen
Kies een willekeurige knoop van de graaf bijvoorbeeld de knoop E.
Bepaal vanuit deze knoop E de kortste verbinding. In dit geval de boog naar de knoop C
Kies vervolgens vanuit de knopen C en E de kortste boog, dit is de boog naar de knoop B.
Herhaal deze werkwijze door de kortste bogen vanuit E, C en B toe te voegen.
Hou er ook rekening mee dat er geen cykel (kring) mag ontstaan omdat er gezocht wordt naar een
opspannende boom.
Er zijn nu twee mogelijkheden. Ofwel voeg je A toe of D.
Kies A en voeg als laatste nog de knoop D toe.
t
e
n
.
o
l
e
h
t
a
m
.
w
Gewicht minimale opspannende boom is 1 + 2 +2 +3 + 2 = 10 w
w
GeoGebra bestand link: https://www.geogebra.org/m/bu3cfhm4
© 2021 Ivan De Winne ivan@mathelo.net 6
