Page 10 - Grafentheorie HS 4 Hamiltongrafen

Grafentheorie

Criterium 4:

Men kan ook met volgend criterium onderzoeken of een graaf een Hamiltongraaf is.
Indien een graaf n knopen heeft en m bogen waarbij m ≥ (n²-n+6)/2 dan is dit een Hamiltongraaf.

OEFENING:

Maak gebruik van de 4 criteria om te onderzoeken of onderstaande graaf een Hamiltongraaf is.
Beantwoord volgende vragen:
1. Is deze graaf volledig? Criterium 1

2. Is voldaan aan de voorwaarden van de stelling van Ore? Criterium 2
3. Is voldaan aan de voorwaarden van de stelling van Dirac? Criterium 3

4. Is voldaan aan het vierde criterium? Criterium 4

Antwoord:
1 Geen volledige graaf omdat niet alle knopen onderling twee aan twee verbonden zijn.
NIET voldaan aan criterium 1
2 Aantal knopen n = 20, graden van alle knopen is 3
Som van twee niet aangrenzende knopen is altijd 6
Deze som is kleiner dan 20
Niet voldaan aan criterium 2

t
3 Graden van alle knopen is 3
e
Helft van aantal knopen is 10 n
3 <10 . o
Niet voldaan aan criterium 3 l
e
4 Aantal bogen m = 30, aantal knopen n = 20 h
t
Niet voldaan aan criterium 4 m ≥ (n²-n+6)/2 a
m

.
Ondanks het feit dat er niet voldaan is één van deze 4 criteria is dit toch een Hamiltongraaf. w
Dit zijn voldoende maar geen nodige voorwaarden! w
w

© 2021 Ivan De Winne ivan@mathelo.net 9