01:640:103 Chap.9 Hamilton Circuits and the Traveling Salesman Problem
Hamilton Circuits and the Traveling Salesman Problem
Tours as weighted graphs
A trip that visits several cities and returns home can be drawn as a graph: cities are vertices, direct routes are edges, and each edge carries a weight such as a fare, a distance or a travel time. A Hamilton circuit visits every vertex exactly once and returns to the start, and the Traveling Salesman Problem asks for a Hamilton circuit of least total weight.
It sounds routine, but in general it is very hard, and mathematicians are still working on it.
Exact but slow
In a complete graph with N vertices and a fixed starting vertex there are (N − 1)! Hamilton circuits, counting a circuit and its mirror image separately. The Brute Force Algorithm totals every one and picks the cheapest, and it is the only method known to guarantee an optimal circuit.
It is also impractical beyond a handful of cities, because eleven cities already give 3,628,800 circuits.
Fast but approximate
Nearest Neighbor starts at one vertex and always travels to the cheapest unvisited vertex. Repetitive Nearest Neighbor runs that from every vertex and keeps the cheapest result, rewritten to start where the question requires.
Cheapest Link ignores the start and adds edges in increasing order of weight, skipping any that would give a vertex three edges or close a circuit too early.
All three are efficient, none is guaranteed optimal, and neither of the last two always beats the other.
Writing circuits and reference points
A circuit written from a different starting vertex is the same circuit: A, B, C, D, A and C, D, A, B, C use the same edges in the same direction.
A circuit written in reverse, its mirror image, costs the same but counts as a different circuit in the course's convention, which is why five towns give 24 circuits from a fixed start rather than 12. When an algorithm produces a circuit starting somewhere else, rewrite it to begin at the town the question names; the edges and the total stay the same.
A cost table is often easier to read than a drawn graph once there are five or more towns.
What this chapter covers
- 01
Graphs, weights and circuits
- 02
Hamilton circuits and the Traveling Salesman Problem
- 03
Counting circuits with factorials
- 04
Brute Force and Nearest Neighbor
- 05
Repetitive Nearest Neighbor and Cheapest Link
Worked example · free
Nearest Neighbor on four cities
- 3From A the cheapest fare is B (70); from B, C (60); from C, D (80); then return D to A (90).
- 1The Nearest Neighbor circuit A, B, C, D, A costs 70 + 60 + 80 + 90 = 300.
- 2Brute Force lists 3! = 6 circuits; the cheapest also costs 300.
Key terms
- Weighted graph
- A weighted graph is a set of vertices joined by edges, each edge carrying a cost, distance or time.
- Hamilton circuit
- A Hamilton circuit is a route that visits every vertex exactly once and returns to its start.
- Brute Force Algorithm
- The Brute Force Algorithm totals every Hamilton circuit and selects one of least weight.
- Cheapest Link
- Cheapest Link builds a circuit from the lowest-weight edges, skipping any that break circuit rules.
- Nearest Neighbor
- Nearest Neighbor builds a circuit by always travelling to the cheapest unvisited vertex from the current one.
- Complete graph
- A complete graph has an edge joining every pair of its vertices, like cities with direct flights between all of them.
Hamilton Circuits and the Traveling Salesman Problem FAQ
How many Hamilton circuits start at a given city when there are six cities?
Five factorial, 5 × 4 × 3 × 2 × 1 = 120, because the other five cities can be visited in any order. Mirror images are counted separately, even though they cost the same, so a table of costs will show each total twice.
Why is Repetitive Nearest Neighbor often better than one Nearest Neighbor run?
A single run depends heavily on its starting city and can be forced into an expensive final flight. Running from every city gives several candidates, and keeping the cheapest usually lowers the cost, though still without a guarantee.
When must I use the Brute Force Algorithm?
Whenever a question asks for an optimal Hamilton circuit. The heuristics are efficient but can miss the cheapest circuit, so only an exhaustive check of every circuit from the starting vertex proves optimality.
Exam move
Keep the fare table beside the graph, list circuits systematically for Brute Force, and for every heuristic write the edges in the order the algorithm chose them.
Working through Hamilton Circuits and the Traveling Salesman Problem in 01:640:103? Sia is AskSia’s AI Mathematics tutor — ask any 01:640:103 Hamilton Circuits and the Traveling Salesman Problem question and get a clear, step-by-step explanation grounded in how 01:640:103 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
