Travelling Salesman Problem Topic Review summary

Key learning points

• Classical TSP: visit each vertex once and return (Hamiltonian cycle) on a complete network.
• Practical TSP allows repeating vertices if the table is not complete — use shortest paths first.
• Nearest neighbour gives a quick upper bound (tour).
• Lower bounds: e.g. MST on $n-1$ vertices plus two cheapest links to the removed vertex.
• State whether your tour is optimal or only bounded.

Worked example 1 — NN

Nearest neighbour from A.

Working

Produces an upper bound.

Worked example 2 — Lower bound

Role of an MST in TSP bounds.

Working

Compare with NN upper bound.

Worked example 3 — Practice point 1

Apply this idea from the Topic Review: Classical TSP: visit each vertex once and return (Hamiltonian cycle) on a complete network.

Working

Attempt without notes, then check the answers PDF.

Worked example 4 — Practice point 2

Apply this idea from the Topic Review: Practical TSP allows repeating vertices if the table is not complete — use shortest paths first.

Working

Attempt without notes, then check the answers PDF.

Scaffolded Learning Sheet and answers (PDFs)

This page is a short, searchable overview for revision and search engines. Use the Scaffolded Learning Sheet first, then the Answers PDF for a full written solution. The printable PDFs remain the main classroom resource.