Page 9 - Grafentheorie HS 4 Hamiltongrafen

Grafentheorie

Criterium 3:
Stelling van Dirac (voldoende voorwaarde)

Indien een graaf n knopen heeft met n ≥ 3 en voor elke knoop geldt dat graad van deze knoop ≥ n/2
dan is dit een Hamiltongraaf.

Er geldt immers voor twee (niet aangrenzende) knopen A en B dat deg(A) + deg(B) ≥n/2 + n/2 = n (Ore)
Voorbeeld:

Aantal knopen n = 4
Graden van alle
knopen

deg(A) = 3
deg(B) = 3
deg(C) = 3

deg(D) = 3
3 ≥ n/2

3 ≥ 4/2
3 ≥ 2
Hamiltongraaf
ABDCA

GeoGebra bestand link: https://www.geogebra.org/m/vseebyjy

Opmerking:
Indien voldaan is aan de voorwaarden van de stelling van Dirac dan is de graaf een Hamiltongraaf en kan
er een Hamiltoncykel gevonden worden.
Deze voorwaarden zijn VOLDOENDE maar niet NODIG zoals blijkt uit volgend voorbeeld.

Aantal knopen n = 5
Graden van de knopen

deg(E) = 3 en deg(F) = 3

deg(I) = 4 t
e
deg(H) = 2 en deg(G) = 2 n
.
2 ≥ 5/2 o
l
e
NIET voldaan aan alle h
voorwaarden t
a
MAAR toch een m
Hamiltongraaf FHIGEF .
w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 8