Route inspection and the travelling salesperson flashcards

Test yourself one card at a time: say the answer, flip, then mark it. Cards you know drop out; the rest come back until you know them. Your progress stays in this browser.

Route inspection problem (Chinese postman)
Find the shortest route that travels along every arc of a network at least once (usually returning to the start).
Odd vertex
A vertex whose degree (number of arc-ends at it) is odd.
Eulerian network
A connected network in which every vertex has even degree: there is a closed route using every arc exactly once.
Semi-Eulerian network
A connected network with exactly two odd vertices: a route using every arc exactly once exists, starting at one odd vertex and finishing at the other.
Travelling salesperson problem
Find the shortest tour that visits every vertex and returns to the start.
Classical vs practical travelling salesperson problem
Classical: each vertex visited exactly once. Practical: each vertex visited at least once (revisiting allowed if shorter).
Table of least distances
A complete table giving the length of the shortest path between every pair of vertices; it turns a practical problem into a classical one.
Residual minimum spanning tree
The minimum spanning tree of the network that remains after one vertex and all its arcs are deleted.
Length of the shortest closed route (route inspection)
Total weight of all arcs + least total weight of the repeated paths joining the odd vertices in pairs. (No — learn it)
Sum of degrees
Sum of degrees = 2 × number of arcs, so the number of odd vertices is always even. (No — learn it)
Number of pairings of four odd vertices P, Q, R, S
Three: PQ + RS, PR + QS, PS + QR. (No — learn it)
Open route with four odd vertices (start and finish free)
Total weight + the shortest single path between any two odd vertices; start and finish at the other two. (No — derive it)
Upper bound from a minimum spanning tree
2 × weight of the MST, then reduce it with shortcuts. (No — learn it)
Lower bound by the residual MST method
Weight of the residual MST (vertex X deleted) + the two least arcs from X. (No — learn it)
Interval for the optimal tour
Largest lower bound ≤ optimal tour length ≤ smallest upper bound. (No — learn it)
Network drawing: a repeated path shown alongside the original arcs
Those arcs are travelled twice; each repeat adds 2 to the degree of every inner vertex and 1 to each end, making the two odd ends even.
Counting visits to a vertex on a closed route
Number of times passed through = (degree + extra arc-ends from repeats) ÷ 2.
Walk round a minimum spanning tree
Goes out and back along every tree arc (each used twice) and visits every vertex; shortcuts jump straight to the next unvisited vertex.
Residual tree + two arcs at the deleted vertex that form a single cycle
Then the lower bound is the length of an actual tour, so that tour is optimal.
Number line with several lower and upper bounds
Only the largest lower bound and the smallest upper bound are used; the optimum lies between them.
Why must arcs be repeated when a network has odd vertices?
A closed route uses arcs in pairs (in and out) at every vertex; an odd vertex cannot be balanced without travelling some arc again.
Why compare all three pairings instead of repeating the two shortest paths?
The two shortest paths may share a vertex (not a pairing), and another pairing can have a smaller total.
Why does nearest neighbour give an upper bound, not the answer?
It produces a real tour, so the optimum is no longer, but its greedy choices do not always give the best tour.
Why use a table of least distances for nearest neighbour?
On an incomplete network the algorithm can get stuck; the complete table always allows a next step and a return.
Why is the residual MST method a lower bound?
Removing X from any tour leaves a spanning path of the rest (≥ residual MST) plus two arcs at X (≥ the two least).
Why can shortcuts only lower the MST upper bound?
In a table of least distances the direct distance is never longer than going via other vertices (triangle inequality).
Network total 57; odd vertices B and E; shortest B–E path is B–C–E = 13. Shortest closed route?
57 + 13 = 70, repeating BC and CE.
Odd vertices A, C, E, F: AC 17, AE 15, AF 20, CE 6, CF 9, EF 5 (shortest paths). Total weight 115. Shortest closed route?
AC + EF = 22, AE + CF = 24, AF + CE = 26; least 22, so 115 + 22 = 137.
Same network (total 115, shortest odd-pair path EF = 5). Shortest route if start and finish may differ?
Repeat EF only: 115 + 5 = 120, starting at A and finishing at C.
Rows A: B32 C11 D25 E21 · B: C29 D37 E13 · C: D33 E19 · D: E26. Nearest neighbour from A?
A C E B D A = 11 + 19 + 13 + 37 + 25 = 105 (upper bound).
An MST has weight 112. Initial upper bound for the travelling salesperson tour?
2 × 112 = 224, before shortcuts.
Deleting A: residual MST weight 36; arcs from A are 13, 9, 21, 24 and 31. Lower bound?
36 + 9 + 13 = 58.
Lower bounds 57, 58, 59; upper bounds 76, 80, 81. Interval for the optimal tour?
59 ≤ optimal ≤ 76.
Answering a four-odd-vertex question
List all three pairings with each shortest path and total, choose the least, name the repeated arcs, then add to the total weight.
Open route with four odd vertices: common slip
Using the best pairing total. Only one path is repeated: the shortest of the six single paths.
Choosing the ‘best’ bounds
Smallest upper bound and largest lower bound, written as an inequality with units.
Interpreting a nearest neighbour tour on the real network
Replace any step that is not a direct arc by its actual path, so revisited vertices appear (e.g. F D A, not F A).

Practise this topicNotes Questions (28)Test builder