D1.3 Route inspection and the travelling salesperson
⤓ Presentation⤓ PowerPointPresentation: opens offline in any browser, simulations live. PowerPoint: editable.
Decision Mathematics 1 (AS), specification sections 3.1–3.2. Degree, Eulerian graphs, Kruskal, Prim and Dijkstra (D1.2) are used here as tools.
What this page covers
6 points
- Route inspection with 0, 2 or 4 odd vertices: why odd vertices force repeats and how to choose the least total repeat
- Route inspection when the route may start and finish at different vertices, including a given start
- The travelling salesperson problem: classical and practical versions, and the table of least distances
- Upper bounds from the nearest neighbour algorithm
- Upper bounds from a minimum spanning tree with shortcuts
- Lower bounds from a residual minimum spanning tree, and the optimal tour as an interval
In one minute
6 points
- Route inspection asks for the shortest route along every arc and back to the start; if every vertex has even degree, its length is simply the total weight of the network.
- Odd vertices come in pairs, and each pair must be joined by a repeated path: route length = total weight + least total of the repeated paths. With four odd vertices compare all three pairings.
- Different start and finish: start and finish at two odd vertices and repeat only the shortest path between the other two (nothing if there are only two odd vertices).
- Travelling salesperson: visit every vertex and return, working from a complete table of least distances; in practice a least distance may pass through other vertices.
- Upper bounds: nearest neighbour, or 2 × MST improved by shortcuts. Lower bound: delete a vertex, find the MST of the rest, add the two shortest arcs from the deleted vertex.
- Best bounds: the largest lower bound and the smallest upper bound, then lower ≤ optimal ≤ upper.
Contents
13 sections
- What does route inspection ask, and why do odd vertices matter?
- How do you deal with four odd vertices?
- What changes if the route can start and finish at different vertices?
- What is the travelling salesperson problem, and what is a table of least distances?
- How do you find upper bounds?
- How does a residual minimum spanning tree give a lower bound?
- How does a full travelling salesperson question fit together?
- Exam tips for D1.3
- Common misconceptions
- How this topic connects
- Key formulae
- Check your understanding
- Specification checklist
What does route inspection ask, and why do odd vertices matter?
A gritter that must drive along every street and a sales rep who must call at every town face different problems. The gritter needs a route covering every arc; the rep needs a tour visiting every vertex. D1 solves the first exactly and bounds the second from above and below.
Every time a route passes through a vertex it uses two arcs there, one in and one out, so a closed route uses an even number of arc-ends at every vertex. If every degree is even the network is Eulerian, and the length is just the total weight. An odd vertex cannot be balanced by the arcs that are there, so some arcs must be travelled twice. Repeating a path between two odd vertices adds one arc-end at each of them and two at every vertex in between, making both even. Since the degrees add to twice the number of arcs, the number of odd vertices is always even: 0, 2, 4, …
A park has footpaths AB (7), AC (5), BC (4), BD (8), CD (10), CE (9), DE (6), DF (5) and EF (3), in hundreds of metres. A warden must walk every path, starting and finishing at the gate A. (a) Find the degree of each vertex and explain why some paths must be walked twice. (b) Find the length of the shortest route and state which paths are walked twice. (c) How many times does the route pass through C?
(a) A 2, B 3, C 4, D 4, E 3, F 2 (sum 18 = 2 × 9 arcs). B and E are odd, so the network is not Eulerian and a closed route must repeat some paths.
(b) Paths from B to E: BCE = 4 + 9 = 13; BDE = 8 + 6 = 14; BDFE = 8 + 5 + 3 = 16. Total = 7 + 5 + 4 + 8 + 10 + 9 + 6 + 5 + 3 = 57, so route = 57 + 13 = 70 (7000 m), with BC and CE walked twice.
(c) C now has 4 + 2 = 6 arc-ends, used two per visit, so 3 times. One possible route: A B C E D B C D F E C A; any route with the right length and arc counts will do.
Repeating the direct arc between two odd vertices without checking for a shorter indirect path, or adding the repeat to the wrong total. List the possible paths with lengths, choose the least, and write "total + repeat = route length" on one line.
How do you deal with four odd vertices?
Four odd vertices P, Q, R, S must be joined in two pairs, and there are exactly three ways: PQ + RS, PR + QS, PS + QR. A quick way to list them is to fix the first odd vertex and pair it with each of the others in turn. For each pairing find the shortest path for each pair and add them; list all three, even if one looks obviously best, because the working is part of the answer. Repeat the pairing with the least total.
Cycle lanes have arcs AB (9), AD (7), AG (15), BC (8), BD (10), BE (11), CE (6), CF (9), DE (8), DG (9), EF (5), EG (7) and FG (11), in km, total 115 km. A sweeper must travel every lane, starting and finishing at its depot D. (a) Identify the odd vertices. (b) Find the length of the shortest route, stating the arcs repeated. (c) How many times does the sweeper pass through B?
(a) A 3, B 4, C 3, D 4, E 5, F 3, G 4, so A, C, E, F are odd.
(b) AC + EF = 17 (ABC) + 5 = 22; AE + CF = 15 (ADE) + 9 = 24; AF + CE = 20 (ADEF) + 6 = 26. Repeat AB, BC and EF: route = 115 + 22 = 137 km.
(c) B has degree 4 and gains 2 (AB and BC repeated): 6 arc-ends, so 3 times. The depot D is even and plays no special part: a closed route has the same length from any start.
Set the pairings out as three lines, each "pair + pair = total", with the route of any indirect path in brackets. It shows the comparison the question is testing, and a slip in one path is easy to spot.
What changes if the route can start and finish at different vertices?
If the route need not return, the start and finish may keep odd degree: the route leaves the start once more than it arrives, and arrives at the finish once more than it leaves.
- Two odd vertices: start at one, finish at the other, and repeat nothing: the network is semi-Eulerian, and the length is the total weight.
- Four odd vertices: two can be the start and finish, so only the other two need joining. Repeat the single shortest path between any two of the four, and start and finish at the remaining two. That means comparing all six paths, not the three pairings.
- Start fixed at an odd vertex: only three options remain: finish at each other odd vertex in turn, repeating the path between the two that are left.
For the cycle lanes of worked example 2 (total 115 km, odd vertices A, C, E, F), the sweeper no longer has to return to its depot. (a) Find the shortest route length and where it should start and finish. (b) The sweeper must now start at E. Where should it finish, and how long is the route?
(a) Shortest paths: AC 17, AE 15, AF 20, CE 6, CF 9, EF 5. Repeat the least: 115 + 5 = 120 km, from A to C (or the reverse).
(b) Finish A: repeat CF = 9, giving 124; finish C: repeat AF = 20, giving 135; finish F: repeat AC = 17, giving 132. Finish at A; 124 km. Fixing the start costs 4 km, because E is one end of EF, the cheapest path that would otherwise be repeated.
Using the least pairing total (22) for an open route. With a different start and finish only one path is repeated, so repeat the shortest of the six (5).
What is the travelling salesperson problem, and what is a table of least distances?
No efficient algorithm is known that always finds the optimal tour for large networks: the number of tours grows factorially. D1 therefore finds an upper and a lower bound. To turn a practical problem into a classical one, replace the network by a complete table of least distances: every pair of vertices with the length of the shortest path between them. The table satisfies the triangle inequality (going direct is never longer than going via a third vertex). After solving, interpret any entry that is not a direct arc: that step passes through other vertices.
Towns A–F are joined by roads AB (13), AC (9), AD (21), BC (8), BE (11), CD (14), CE (16), DE (7), DF (10) and EF (12), in km. Complete the table of least distances, explaining any entry that is not a direct road.
Copy the direct roads, checking none is beaten by a route through another town (AD: direct 21, via C 23, so 21 stays). Then fill the gaps: AE = 24 (A–B–E; A–C–E is 25); AF = 31 (A–D–F; A–C–D–F is 33); BD = 18 (B–E–D); BF = 23 (B–E–F); CF = 24 (C–D–F).
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 13 | 9 | 21 | 24 | 31 |
| B | 13 | — | 8 | 18 | 11 | 23 |
| C | 9 | 8 | — | 14 | 16 | 24 |
| D | 21 | 18 | 14 | — | 7 | 10 |
| E | 24 | 11 | 16 | 7 | — | 12 |
| F | 31 | 23 | 24 | 10 | 12 | — |
Bold entries are not direct roads; a tour using one passes through another town.
How do you find upper bounds?
The nearest neighbour algorithm
Choose a start vertex; repeatedly move to the nearest vertex not yet visited; when all are visited, return to the start. The result is a genuine tour, so the optimal tour is no longer: its length is an upper bound. Use the table of least distances so every vertex can be reached at every step (on the original network the algorithm can get stuck or fail to return). Different starts usually give different tours; the best upper bound is the smallest. Greedy choices can force an expensive final step, which is why the bound is often well above the optimum.
Using the table in worked example 4: (a) apply nearest neighbour from A to find an upper bound; (b) interpret the tour on the road network; (c) repeat (a) from B and state the better upper bound.
(a) A → C (9) → B (8) → E (11) → D (7) → F (10) → A (31): upper bound 76 km.
(b) F → A is A–D–F reversed, so the route is A C B E D F D A (D visited twice).
(c) B → C (8) → A (9) → D (21) → E (7) → F (12) → B (23) = 80 km. Better upper bound 76 km. At C (from B) the nearest unvisited town is A (9), not D (14): read the whole row and ignore towns already visited.
A minimum spanning tree with shortcuts
Walking all the way round a minimum spanning tree and back uses every tree arc twice and visits every vertex, so 2 × MST weight is an upper bound. That walk revisits vertices. A shortcut jumps straight to the next unvisited vertex using the table; by the triangle inequality it is never longer than the arcs it replaces, so shortcuts can only lower the bound. Questions often say "use shortcuts to reduce the upper bound to below …": show the tour and its length.
This six-town table (km) is a classical problem: every entry is already a least distance. (a) Use Prim's algorithm from P to find a minimum spanning tree, listing arcs in order, and state its weight. (b) Hence find an initial upper bound. (c) Use shortcuts to reduce the upper bound below 170 km.
| P | Q | R | S | T | U | |
|---|---|---|---|---|---|---|
| P | — | 33 | 26 | 24 | 43 | 40 |
| Q | 33 | — | 21 | 35 | 30 | 46 |
| R | 26 | 21 | — | 29 | 18 | 31 |
| S | 24 | 35 | 29 | — | 39 | 23 |
| T | 43 | 30 | 18 | 39 | — | 34 |
| U | 40 | 46 | 31 | 23 | 34 | — |
(a) PS (24), SU (23), PR (26), RT (18), RQ (21): weight 112 km.
(b) 2 × 112 = 224 km (the walk P S U S P R T R Q R P).
(c) U → R replaces U–S–P–R (23 + 24 + 26 = 73) by 31; T → Q replaces T–R–Q (39) by 30; Q → P replaces Q–R–P (47) by 33. Tour P S U R T Q P = 24 + 23 + 31 + 18 + 30 + 33 = 159 km < 170. Branch order matters: P S U R Q T P gives 172 km, which misses the target.
How does a residual minimum spanning tree give a lower bound?
Why it works: any tour with X removed becomes a path through all the other vertices, which is a spanning tree, so it is at least the residual MST; the tour also uses exactly two arcs at X, which are at least the two shortest. If the residual tree plus the two arcs happens to form a tour, that tour is optimal; likewise if the best lower bound equals an upper bound.
For the six towns of worked example 4: (a) by deleting A, use Kruskal's algorithm on the table to find a lower bound; (b) deleting B instead, find another lower bound; (c) using worked example 5, write down the smallest interval for the optimal tour.
(a) Kruskal on B–F: DE (7), BC (8), DF (10), BE (11), which already join all five, so residual MST = 36. Add AC = 9 and AB = 13: lower bound 58 km.
(b) Residual MST: DE (7), AC (9), DF (10), CD (14) = 40; add BC = 8 and BE = 11: 59 km.
(c) Largest lower bound 59, smallest upper bound 76: 59 ≤ optimal tour ≤ 76 (km). Checking all 60 tours shows the optimum is 69 km (A B E F D C A), inside the interval; you are never expected to do this.
Choosing the smallest lower bound ("it is safer") or the largest upper bound. Both are true, but the interval should be as narrow as possible: largest lower bound, smallest upper bound.
How does a full travelling salesperson question fit together?
A full question starts from a practical network, completes the table of least distances, finds an upper bound, interprets it, finds a lower bound and finishes with an interval. Each step uses the previous one, so keep tables and lists clear.
A technician must visit masts H, J, K, L, M and N, starting and finishing at H. Tracks: HJ (17), HK (23), HN (11), JK (19), JL (8), KL (18), KM (22), LM (13), LN (19), MN (29), in km. Part of the table of least distances:
| H | J | K | L | M | N | |
|---|---|---|---|---|---|---|
| H | — | 17 | 23 | 11 | ||
| J | 17 | — | 19 | 8 | 21 | 27 |
| K | 23 | 19 | — | 18 | 22 | |
| L | 8 | 18 | — | 13 | 19 | |
| M | 21 | 22 | 13 | — | 29 | |
| N | 11 | 27 | 19 | 29 | — |
(a) Find HL, HM and KN, showing the routes. (b) Use nearest neighbour from H to find an upper bound. (c) Interpret the tour on the network. (d) From J, nearest neighbour gives 104 km. State, with a reason, the better upper bound. (e) By deleting L, find a lower bound. (f) Give the smallest interval for the optimal tour.
(a) HL = 25 (H–J–L; H–N–L is 30, H–K–L is 41); HM = 38 (H–J–L–M); KN = 34 (K–H–N; K–L–N is 37).
(b) H → N (11) → L (19) → J (8) → K (19) → M (22) → H (38): 117 km.
(c) M → H is not a track: use M–L–J–H, so H N L J K M L J H (L and J passed twice).
(d) 104 km, because it is the smaller upper bound (a tour of that length exists).
(e) Kruskal on H, J, K, M, N: HN (11), HJ (17), JK (19), JM (21) = 68; two least from L: LJ = 8, LM = 13: 89 km. JM = 21 is a table entry even though its route passes through L; use the table as written.
(f) 89 ≤ optimal tour ≤ 104 (km). The optimal tour is 101 km, inside the interval.
Exam tips for D1.3
For four odd vertices, write all three pairings with totals, then state the least and name the repeated arcs. A bare "repeat AB, BC, EF" with no comparison does not show the algorithm.
Routes and visit counts depend on which arcs are repeated, so name them ("AB, BC and EF"), not only the extra length.
"Best" means the narrowest interval. Write the answer as an inequality with units, e.g. 59 ≤ T ≤ 76.
Write the tour with each step's length (A → C (9) → B (8) …) and the total, so each greedy choice is visible and no vertex is revisited.
When a tour uses a least distance that is not a direct arc, replace the step by the actual path so the vertices passed through appear (F D A, not F A).
Common misconceptions
| Misconception | Why it is wrong | Correct idea |
|---|---|---|
| The repeated path between two odd vertices is the direct arc. | The shortest path may be indirect, or there may be no direct arc (worked example 1 has no BE; B–C–E = 13 beats B–D–E = 14). | Find the shortest path by inspection or Dijkstra. |
| With four odd vertices, repeat the two shortest single paths. | They may share a vertex and not form a pairing, or another pairing may be cheaper. | Compare the totals of the three pairings. |
| An open route still uses the best pairing. | Start and finish can stay odd, so only one path is repeated. | Repeat the shortest of the six paths; start and finish at the other two. |
| The nearest neighbour tour is the optimal tour. | It is greedy and can end with a long return step. | It gives an upper bound only. |
| A lower bound must be the length of a real tour. | The residual tree plus two arcs is usually not a tour. | It shows no tour is shorter; it equals the optimum only if it forms a tour. |
| Classical and practical problems always have the same answer. | Revisiting vertices can be shorter on the original network. | Solve with the table of least distances, then interpret the tour. |
How this topic connects
D1.2 Graphs, minimum spanning trees and Dijkstra
The Eulerian test decides whether anything is repeated; Dijkstra finds shortest paths between odd vertices and builds the table of least distances; Prim and Kruskal give the trees for both bounds.
D1.1 Algorithms
Nearest neighbour is greedy, like first-fit bin packing: fast but not always optimal, and judged against a bound just as a packing is judged against the lower bound for bins.
P1 inequalities, and D1.4–D1.5
The answer is an interval, written with the same care as any inequality. Like the TSP bounds, critical path analysis and linear programming ask you to model, apply an algorithm and interpret the result in context.
Key formulae
| Formula | Use | In the formulae list? |
|---|---|---|
| sum of degrees = 2 × number of arcs | shows the number of odd vertices is even; checks degree counts | No — learn it |
| closed route = total weight + least total of repeated paths | route inspection length (0, 2 or 4 odd vertices) | No — learn it |
| 4 odd vertices: 3 pairings (PQ + RS, PR + QS, PS + QR) | listing the options to compare | No — learn it |
| open route = total weight + shortest single path between odd vertices | start and finish at different vertices (four odd vertices); two odd vertices: total weight | No — derive it |
| times a vertex is passed through = (degree + repeated arc-ends) ÷ 2 | counting visits on a closed route | No — derive it |
| upper bound = 2 × MST weight (then shortcuts) | minimum spanning tree method | No — learn it |
| lower bound = residual MST + two least arcs from the deleted vertex | residual minimum spanning tree method | No — learn it |
| largest lower bound ≤ optimal tour ≤ smallest upper bound | the interval for the optimal tour | No — learn it |
Check your understanding
1. A network has all vertices of even degree and total weight 84. What is the shortest closed route covering every arc?
84. The network is Eulerian, so a closed route uses every arc exactly once and nothing is repeated.
2. A graph has degrees 3, 3, 3, 3, 2 and 2. How many arcs does it have, and how many pairings must be compared?
The degrees add to 16, so 8 arcs. Four odd vertices give three pairings.
3. A route inspection network has odd vertices P and Q only, and the route may start and finish anywhere. Where should it start and finish, and what is repeated?
Start at P and finish at Q (or the reverse). Nothing is repeated: the network is semi-Eulerian, so the length is the total weight.
4. A lower bound of 141 and an upper bound of 141 are found for a travelling salesperson problem. What can you conclude?
The optimal tour is exactly 141, and the tour giving the upper bound is optimal.
5. Why is nearest neighbour usually applied to a table of least distances rather than the original network?
On an incomplete network the current vertex may have no arc to an unvisited vertex, or the last vertex no arc back to the start, so the algorithm stalls. The table is complete, so every step is possible.
Specification checklist
- (D1 3.1) I can explain why odd vertices force arcs to be repeated, and why the number of odd vertices is even.
- (D1 3.1) I can find the shortest closed route covering every arc of a network with two odd vertices, naming the repeated arcs.
- (D1 3.1) I can list the three pairings of four odd vertices, compare their totals and find the shortest route length.
- (D1 3.1) I can find the shortest route when start and finish may differ, or when only the start is fixed.
- (D1 3.1) I can find the number of times a vertex is visited, and write down a possible route.
- (D1 3.2) I can explain the classical and practical travelling salesperson problems and build a complete table of least distances.
- (D1 3.2) I can use nearest neighbour to find an upper bound and interpret the tour on the original network.
- (D1 3.2) I can find an upper bound from a minimum spanning tree and improve it with shortcuts.
- (D1 3.2) I can find a lower bound using a residual minimum spanning tree.
- (D1 3.2) I can choose the best bounds and give the optimal tour as an interval, recognising when the bounds show a tour is optimal.