Lesson 8: Hamiltonian paths and cycles

A vet's round trip — the shortest Hamiltonian cycle

SkillHamiltonian paths and cycles

Worked example

  • Complex familiar

A mobile vet based in town TT must visit four farms, PP, QQ, RR and SS, once each and then return to TT. Travel times, in minutes, are shown. Find the quickest round trip and its total time.

1 of 6 steps
  1. 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.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. List the Hamiltonian cycles systematically, grouped by the pair of edges used at the starting vertex.

  2. Count a cycle and its reverse once.

  3. Total each cycle and choose the least.

Watch out for

  • Forgetting the return leg. The path TT–PP–QQ–RR–SS takes 36 minutes, but the trip is not over until the vet is back at TT.

Save your progress with a free account