A gritter must drive down every road and come back: Imagine a gritting lorry that must drive along every road in a town and return to the depot, covering the least total distance.
If you could re-enter and leave each junction an even number of times, you'd traverse every road exactly once (an Eulerian circuit) and the answer would just be the sum of all the edges. That works precisely when every vertex has even degree.
A vertex with odd degree is the problem: you must walk along some roads twice to come back to it. The route-inspection (Chinese postman) algorithm decides which roads to repeat.
The recipe: 1. Find every odd-degree vertex (a connected graph always has an even number of them).
2. Find the shortest path between each pair of odd vertices.
3. Pair the odd vertices so the total repeated distance is least, and add that to the sum of all the edges.
Shortest closed walk = (sum of all edges) + (cheapest pairing of the odd vertices).
IB-style question — Chinese postman
A park-keeper must inspect every path and return to the start. Path lengths (m): AB = 4, AC = 5, BC = 3, BD = 6, CE = 7, DE = 4, DF = 5, EF = 6.
The sum of all the paths is 40 m. Find the length of the shortest closed inspection walk.
Step by step
- Find the degree of each vertex.
- Odd-degree vertices: B, C, D, E (four of them).
- Shortest paths between the odd pairs: BC = 3, BD = 6, BE = 10 (B–D–E), CD = 9 (C–B–D), CE = 7, DE = 4.
- Compare the 3 ways to pair all four: (BC + DE) = 7, (BD + CE) = 13, (BE + CD) = 19. Cheapest is BC + DE = 7.
- Repeat those shortest paths on top of every edge.
Final answer
Shortest closed inspection walk = 47 m (repeat the B–C and D–E paths). Every path is covered, ending back at the start.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
Visit every city once and come home — as short as possible: The travelling salesman problem (TSP) asks for the shortest closed route that visits every vertex exactly once and returns to the start (a Hamiltonian cycle). Unlike the postman, here you care about the vertices, not every edge.
There is no quick formula for the exact best tour, so the exam asks you to trap it between two bounds: an upper bound (an actual route you can find) and a lower bound (a value the best tour cannot beat).
Nearest-neighbour algorithm → an upper bound: Start at the given vertex. Repeatedly go to the nearest vertex not yet visited. When all are visited, return to the start. This gives a genuine route, so its length is an upper bound for the best tour (the best tour is at most this long).
It needs the complete graph (a distance between every pair) — fill any gap with the shortest path first.
IB-style question — nearest-neighbour upper bound
Five towns A, B, C, D, E have these distances (km):
AB = 20, AC = 35, AD = 42, AE = 28, BC = 34, BD = 30, BE = 25, CD = 12, CE = 40, DE = 22.
Use the nearest-neighbour algorithm starting at A to find an upper bound for the travelling-salesman tour.
Step by step
- From A, the nearest is B (20).
- From B, nearest unvisited is E (25).
- From E, nearest unvisited is D (22).
- From D, the only one left is C (12).
- Return from C to A (35).
- Add the five legs.
Final answer
Upper bound = 114 km (route A → B → E → D → C → A). The best possible tour is at most 114 km.