Page 5 - Grafentheorie HS 4 Hamiltongrafen

Grafentheorie

4.3 Onderscheid tussen Eulergrafen en Hamiltongrafen

4.3.1 Definities

Definitie 1:
Een pad is een wandeling langs verschillende knopen, zonder dat dezelfde knoop herhaald wordt.

Definitie 2:
Een cykel is een wandeling langs verschillende knopen, zonder dat dezelfde knoop herhaald wordt
en waarbij men eindigt in de startknoop. Men zegt ook dat een cykel een gesloten pad is.

https://www.geogebra.org/m/nym2ffqv
Definitie 3:

Een Hamiltonpad is een “open” pad dat ALLE knopen van de graaf precies één keer passeert.
Definitie 4:
Een Hamiltoncykel is een cykel die over ALLE knopen van de graaf precies één keer passeert (en waarbij
men opnieuw eindigt in de startknoop).

Indien in een graaf een Hamiltoncykel kan gevonden worden dan is dit een Hamiltongraaf.
Opmerking:

Voor een Eulergraaf moet men nagaan of er een wandeling bestaat waarbij men de BOGEN PRECIES 1
KEER gebruikt om een Eulercircuit te bekomen.

Voor een Hamiltongraaf moet men nagaan of er een wandeling bestaat waarbij men de KNOPEN
PRECIES 1 KEER gebruikt om een Hamiltoncykel te bekomen.

Onderzoek of onderstaande grafen Eulergrafen of Hamiltongrafen zijn.

Teken het bijhorende Eulercircuit en Hamiltoncykel.
t
e
n
.
o
l
e
h
t
a
m
.
w
Hamiltongraaf maar geen Eulergraaf Eulergraaf maar geen Hamiltongraaf w
w
GeoGebra bestand link: https://www.geogebra.org/m/c5k5hcua

© 2021 Ivan De Winne ivan@mathelo.net 4