Page 6 - Grafentheorie HS 4 Hamiltongrafen

Grafentheorie

4.3.2 Aantal Hamiltonpaden

Voor een graaf met een klein aantal knopen is het nog vrij eenvoudig om ALLE Hamiltonpaden te vinden.
Voor een Hamiltonpad moet de startknoop niet gelijk zijn aan de eindknoop.
Voorbeeld 1:

Voorbeeld 2: Volledige grafen

Beschouw een volledige graaf met 4 knopen. Kies als startknoop A.
Bepaal het aantal Hamiltoncykels waarbij je alle knopen passeert en eindigt in de startknoop.

Men kan ook rekening houden met de startknoop waardoor het aantal Hamiltoncykels 4 x 3 = 12 wordt.

Indien men bovendien geen rekening houdt met symmetrie dan geeft dit uiteindelijk 24 mogelijkheden.

Mogelijke Hamiltoncykels voor deze situatie:

ABCDA, ADCBA, BCDAB, BADCB, CDABC en CBADC t
e
Analoog voor de twee andere mogelijkheden geeft dit in totaal n
voor deze erg eenvoudige graaf al 4x3x2 = 24 mogelijkheden. .
o
l
e
h
t
a
m
.
Een veralgemening volgt later bij de bespreking van het “Handelsreizigersprobleem” . w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 5