Page 4 - Grafentheorie HS 6 Bomen

HS 6 Bomen

6.2.4 Opspannende boom

Een opspannende boom van een graaf is een deelgraaf van een graaf, indien aan de volgende
voorwaarden voldaan is:
De deelgraaf bevat alle knopen van de oorspronkelijke graaf.

De deelgraaf is samenhangend.
De deelgraaf bevat geen cykels.

Voorbeeld
Gegeven een graaf

… en een aantal opspannende bomen van deze graaf

6.2.5 Minimaal opspannende boom

Een graaf waarbij er getallen staan op de bogen noemt men een gewogen graaf. De getallen noemt men
de gewichten van de bogen.

t
e
n
.
o
l
e
h
t
a
m
.
w
Er bestaan meerdere opspannende bomen van deze graaf waarvan de lengte verschillend is. w
w

© 2021 Ivan De Winne ivan@mathelo.net 3