Topic summary · Decision maths (D2)
Travelling Salesman Problem summary
The travelling salesman problem seeks a shortest Hamiltonian tour. Upper and lower bounds frame the optimum on small networks.
Files: D2-Travelling Salesman Problem.pdf · D2-Travelling Salesman Problem answers.pdf · free public downloads · diagrams in the PDFs
Key learning points
- Nearest neighbour produces a tour (upper bound).
- MST-based arguments give lower bounds.
- Exam networks are small — show bound calculations clearly.
- Distinguish a closed tour from an open path.
Worked example 1 — Bounds
Tour length 48, lower bound 45. What follows?
Working
Tighten bounds to locate the optimum.
Worked example 2 — Nearest neighbour produces a tour (upper bound)
Use this method from the Travelling Salesman Problem sheet: Nearest neighbour produces a tour (upper bound).
Working
Each key learning point matches a question type on the printable worksheet.
Worked example 3 — MST-based arguments give lower bounds
Use this method from the Travelling Salesman Problem sheet: MST-based arguments give lower bounds.
Working
Each key learning point matches a question type on the printable worksheet.
Worked example 4 — Exam networks are small — show bound calculations clear
Use this method from the Travelling Salesman Problem sheet: Exam networks are small — show bound calculations clearly.
Working
Each key learning point matches a question type on the printable worksheet.
Worked example 5 — Distinguish a closed tour from an open path
Use this method from the Travelling Salesman Problem sheet: Distinguish a closed tour from an open path.
Working
Each key learning point matches a question type on the printable worksheet.
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.