Page 7 - Grafentheorie HS 4 Hamiltongrafen

Grafentheorie

4.4 Criteria voor het bestaan van Hamiltongrafen

Het aantonen van het bestaan van een Eulerspoor of Eulercircuit is vrij eenvoudig zoals werd besproken
in hoofdstuk 2 paragraaf 2.2.2.
Er bestaat spijtig genoeg geen eenvoudig criterium waarmee men het bestaan van een Hamiltongraaf
kan aantonen. Onderstaande eigenschappen kunne wel van nuttig komen bij het opsporen van een
Hamiltonpad of Hamiltoncykel.

4.4.1 Eenvoudige eigenschappen van Hamiltongrafen

Eigenschap 1:

Een graaf met (minstens) 1 knoop van graad 1 is geen Hamiltongraaf.

Je kan wel starten in A (of E) maar nooit eindigen in A.

Eigenschap 2:
Indien de graad van de knoop van een graaf gelijk is aan 2 dan moet de boog die aankomt en de boog
die vertrekt een deel zijn van een eventuele Hamiltoncykel.

4.4.2 Stellingen i.v.m. Hamiltongrafen

Criterium 1: (voldoende voorwaarde)
Als een graaf volledig is (n ≥ 3) dan is dit een Hamiltongraaf.

Omdat bij een volledige graaf ALLE knopen met elkaar verbonden zijn is het steeds mogelijk om van de t
e
ene knoop naar een andere knoop te gaan zonder gebruik te maken van een knoop die al gepasseerd n
werd. Er kunnen verschillende Hamiltoncykels gevonden worden. .
o
l
e
h
t
a
m
.
w
w
w
K5

© 2021 Ivan De Winne ivan@mathelo.net 6