Hamiltonian cycles and the travelling salesman problem questions with answers
Practice questions on Hamiltonian cycles and the travelling salesman problem, from the basics up to exam level, each with a full worked solution. Try one online now, or work through the list below on paper and open the solution to check your working.
Try a question: Hamiltonian cycles and the travelling salesman problem
Free · no sign-up
Answer a real practice question. Get it wrong and MugCorner shows you where it went wrong, with hints and a step-by-step guide.
Worked example
Does the graph shown have a Hamiltonian cycle, a Hamiltonian path but no Hamiltonian cycle, or neither?
Step 1 of 2
The degrees: a vertex of degree 1 can only be the end of a path
Degrees: A 3, B 4, C 3, D 4, E 4
Free account
What you get when you sign in
Everything on this page stays free. An account is where Hamiltonian cycles and the travelling salesman problem practice starts adding up.
✓Endless questions on every chapter, at every level
✓Your mistakes tracked by type, so you see what keeps costing marks
Try a question with marking, hints and the step guide
✓
✓
Endless questions on every chapter, at every level
–
✓
Levels that unlock as you improve
–
✓
Your mistakes tracked by type, so you see what keeps costing marks
–
✓
WA practice papers on the chapters being tested
–
✓
Revision reminders before a topic fades
–
✓
Progress page and leaderboards
–
✓
Questions
Question 1Hamiltonian paths and cycles
Does the graph with this adjacency matrix have a Hamiltonian cycle, a Hamiltonian path but no Hamiltonian cycle, or neither? M=ABCDEA01100B10110C11011D01101E00110
Show the worked solution
Step 1: The degrees: a vertex of degree 1 can only be the end of a pathDegrees: A 2, B 3, C 4, D 3, E 2
Step 2: Try to visit every vertex exactly once (and, for a cycle, get back to the start)A cycle through every vertex: A → B → D → E → C → A
Question 2Hamiltonian paths and cycles
Does the graph shown have a Hamiltonian cycle, a Hamiltonian path but no Hamiltonian cycle, or neither?
Show the worked solution
Step 1: The degrees: a vertex of degree 1 can only be the end of a pathDegrees: A 2, B 3, C 1, D 1, E 1
Step 2: Try to visit every vertex exactly once (and, for a cycle, get back to the start)C, D, E have degree 1: each must be an end of a path, and a path has only two ends
Question 3Upper bound: nearest neighbour
The table shows the least distances, in km, between 5 towns: ABCDEA−9111211B9−898C118−1011D12910−12E1181112− Use the nearest neighbour algorithm, starting at E, to find an upper bound for the travelling salesman problem.
Show the worked solution
Step 1: Nearest neighbour: each time go to the nearest town not yet visited, then back to the startRoute: E → B (8) → C (8) → D (10) → A (12) → E (11)
Step 2: The upper bound: the length of this route8+8+10+12+11=49 km
Question 4Upper bound: nearest neighbour
The table shows the least distances, in km, between 5 towns: ABCDEA−8141410B8−14915C1414−118D14911−12E1015812− Use the nearest neighbour algorithm, starting at D, to find an upper bound for the travelling salesman problem.
Show the worked solution
Step 1: Nearest neighbour: each time go to the nearest town not yet visited, then back to the startRoute: D → B (9) → A (8) → E (10) → C (8) → D (11)
Step 2: The upper bound: the length of this route9+8+10+8+11=46 km
Question 5Lower bound: deleted vertex
The table shows the least distances, in km, between 5 towns: ABCDEA−14141214B14−91510C149−119D121511−13E1410913− By deleting vertex D, find a lower bound for the travelling salesman problem.
Show the worked solution
Step 1: Delete D: a minimum spanning tree of the other towns (Kruskal)Edges: BC (9), CE (9), AB (14)Weight=32
Step 2: Add back the two shortest edges from DDC (11), DA (12)
Step 3: The lower bound32+11+12=55 km
Question 6Lower bound: deleted vertex
The table shows the least distances, in km, between 5 towns: ABCDEA−8121510B8−131311C1213−1510D151315−8E1011108− By deleting vertex A, find a lower bound for the travelling salesman problem.
Show the worked solution
Step 1: Delete A: a minimum spanning tree of the other towns (Kruskal)Edges: DE (8), CE (10), BE (11)Weight=29
Step 2: Add back the two shortest edges from AAB (8), AE (10)