Maths › Decision Mathematics 1 › Route inspection
Route inspection
Walk along every road and come back to where you started. If the network has odd nodes some roads must be walked twice, and the whole problem is choosing which ones.
Builds on Shortest paths: Dijkstra and Floyd and Graphs: order, Eulerian paths and planarity.
IN THIS TOPIC
- Identify the odd nodes and list every possible pairing of them.
- Find the shortest path between each pair and choose the cheapest pairing.
- State the length of the shortest closed route and which edges are repeated.
WHAT YOU PROBABLY THINK
In route inspection you repeat the shortest edges in the network until every node has even order.
Why anything has to be repeated
A closed route using every edge exactly once exists only when every node has even order, since each visit to a node uses two of its edges. Odd nodes therefore force repetition, and repeating an edge is equivalent to adding a duplicate, which raises the order of both its ends by one.
So the job is to pair up the odd nodes and repeat a shortest path between each pair. Not the shortest edges: the shortest path between two odd nodes may run through several edges and through other nodes, and repeating an edge between two even nodes would only make matters worse. The opening claim confuses the two.
WORKED EXAMPLE
Choosing the pairing
The network's odd nodes are A, B, D and E, with shortest paths AB 5, AD 9, AE 13, BD 7, BE 9, DE 9. Find the cheapest pairing.
There are three ways to pair four nodes.
AB with DE: 5 + 9 = 14.
AD with BE: 9 + 9 = 18. AE with BD: 13 + 7 = 20.
The cheapest is AB and DE, adding 14 to the route.
The answer
The length of the shortest closed route is the total weight of all the edges plus the cost of the cheapest pairing. With four odd nodes there are three pairings, which is why the specification caps the number of odd nodes at four unless extra information narrows the choice.
Two special cases are worth having ready. With no odd nodes, nothing is repeated and the answer is simply the total weight. If the route need not return to the start, the two odd nodes at the ends of the walk are left unpaired, so pair the remaining ones as cheaply as possible and start and finish at the two left over.
YOUR TURN
The full answer
The nine edges of the network total 55. Find the length of the shortest closed route travelling along every edge at least once, and say which edges are repeated.
Show the working
The cheapest pairing costs 14.
Total = 55 + 14 = 69.
The repeated edges are AB, and the shortest D to E path, which is D to C to E.
So DC and CE are each walked twice, as is AB, and every other edge exactly once.
THE EXAM BIT
- List the odd nodes first; if there are none, the answer is the total weight and nothing is repeated.
- Write out all three pairings with their costs, even the ones you can see are worse.
- Use shortest paths between odd nodes, which may pass through other nodes.
- State the repeated edges as well as the total; the question almost always asks.
CHECK YOURSELF
A network of total weight 80 has odd nodes P, Q, R, S with shortest paths PQ 6, PR 9, PS 11, QR 8, QS 5, RS 7. Find the shortest closed route.
Show a hint
Three pairings; take the cheapest.
Show the answer
P
Q
+
R
S
=
1
3
,
P
R
+
Q
S
=
1
4
,
P
S
+
Q
R
=
1
9
.
C
h
e
a
p
e
s
t
i
s
1
3
,
s
o
t
h
e
r
o
u
t
e
i
s
8
0
+
1
3
=
9
3
.
Odd nodes force repetition, so pair them up and repeat a shortest path between each pair.
The answer is the total weight of the network plus the cost of the cheapest pairing, and the repeated edges must be named.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Identify the odd nodes and list every possible pairing of them.
- Find the shortest path between each pair and choose the cheapest pairing.
- State the length of the shortest closed route and which edges are repeated.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.