Lesson 8: Hamiltonian paths and cycles
A vet's round trip — the shortest Hamiltonian cycle
SkillHamiltonian paths and cycles
Worked example
A mobile vet based in town must visit four farms, , , and , once each and then return to . Travel times, in minutes, are shown. Find the quickest round trip and its total time.
Step 1: Recognise the problem
Visiting every vertex once and returning to the start is a Hamiltonian cycle. You want the one with the least total time.
Step 2: Organise the trial and error
is joined to , and , so the trip leaves along one of these edges and returns along another. A cycle and its reverse take the same time, so list each cycle once.
Step 3: Cycles that use TP and TQ
Visit and in between: ––––– takes min. (–––… is impossible: there is no edge .)
Step 4: Cycles that use TP and TS
––––– takes min, and ––––– takes min.
Step 5: Cycles that use TQ and TS
––––– takes min. The other order, –––––, would need the edge , which does not exist.
Step 6: Choose the least total
The quickest round trip is –––––, or its reverse, taking 56 minutes.
Answer
––––– (or the reverse), taking 56 minutes.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
List the Hamiltonian cycles systematically, grouped by the pair of edges used at the starting vertex.
Count a cycle and its reverse once.
Total each cycle and choose the least.
Watch out for
Forgetting the return leg. The path –––– takes 36 minutes, but the trip is not over until the vet is back at .