Page 10 - Grafentheorie HS 5 Handelsreizigersprobleem

HS 5 Handelsreizigersprobleem

• Ga vanuit D naar de dichtstbijzijnde knoop C

• Ga vanuit C naar de dichtstbijzijnde knoop B

• Ga tenslotte naar de beginknoop A

De lengte van deze route ABCDEA (Hamiltoncykel) is 30.
Opmerkingen

In totaal kunnen er 12 verschillende Hamiltoncykels doorlopen worden waarbij de lengte korter of
langer kan zijn afhankelijk van de gekozen beginknoop.

Indien als beginknoop B wordt gekozen van is de lengte van de route BEDCAB gelijk aan 32.

t
e
Indien als beginknop D wordt gekozen dan is de lengte van de route DECBAD gelijk aan 29. n
.
ABCDEA 30 ACBDEA 34 o
l
e
ABCEDA 29 ACBEDA 32
h
t
ABDECA 33 ADBECA 35 a
m
ABDCEA 33 ADBCEA 33
.
ABEDCA 32 AEBDCA 36 w
w
ABECDA 31 AEBCDA 32 w
Al naargelang van de gekozen route is de lengte verschillend van minimaal 29 tot maximaal 36.

© 2021 Ivan De Winne ivan@mathelo.net 9