Page 3 - Grafentheorie HS 6 Bomen

HS 6 Bomen

6.2 Opspannende bomen

6.2.1 Deelgraaf van een graaf

Indien men in een graaf een aantal knopen en bijhorende bogen weglaat dan bekomt men een
deelgraaf.
Een graaf H is een deelgraaf van de graaf G indien alle knopen van H ook knopen zijn van G en alle
bogen van H ook bogen zijn van G.

Oorspronkelijke graaf en twee deelgrafen.
6.2.2 Samenhangende grafen

Een graaf is samenhangend indien er tussen elk paar knopen steeds een verbinding (boog) is.

Samenhangende graaf Onsamenhangende graaf

GeoGebra bestand link https://www.geogebra.org/m/s7mf2cw5
6.2.3 Bomen

Een boom is een samenhangende graaf zonder cykels (kringen)

t
e
n
.
o
l
e
h
t
a
Een boom GEEN boom m
.
GeoGebra bestand link: https://www.geogebra.org/m/sfhqeyu5 w
w
Eigenschap w

Indien n het aantal knopen is van een boom en m het aantal bogen dan geldt n = m + 1

© 2021 Ivan De Winne ivan@mathelo.net 2