Practise › Questions › Route inspection
Route inspection questions
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.
6 original questions · 24 marks · the route inspection notes · Decision Mathematics 1
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
Explain why a network with odd nodes cannot be walked using every edge exactly once and returning to the start.
Worked answer
Every visit to a node uses one edge to arrive and one to leave, so a closed trail uses the edges at each node in pairs. A node of odd order would have an edge left over with no partner, so no such trail exists unless every node has even order. B1 for the edges at each node being used in pairs, B1 for the odd node leaving one unpaired.The odd nodes of a network are A, B, D and E, with shortest paths AB 5, AD 9, AE 13, BD 7, BE 9, DE 9. List the three pairings with their costs.
Worked answer
AB with DE: 5 + 9 = 14. AD with BE: 9 + 9 = 18. AE with BD: 13 + 7 = 20. B1 B1 B1 for the three pairings with their costs. Four odd nodes always give exactly three pairings, and the specification caps the number at four for that reason. List all three even when one is obviously worst, since the marks are for the comparison.The nine edges of that network total 55. Find the length of the shortest closed route using every edge at least once, and name the repeated edges, given that the shortest D to E path runs through C.
Worked answer
The cheapest pairing costs 14, so the route is 55 + 14 = 69. The repeated stretches are AB and the shortest D to E path, which is DC and CE. M1 for choosing the cheapest pairing, A1 for 14, A1 for 69, B1 for the repeated edges. Every other edge is walked exactly once, and the route may start anywhere. Name the edges that are repeated as well as the pairing, since the final mark is for them.For the same network, find the shortest route that need not return to the start, and say where it begins and ends.
Worked answer
An open route leaves two odd nodes unpaired, one at each end. To minimise the repetition, pair the two odd nodes with the cheapest connection and leave the others: pairing A with B costs 5, leaving D and E as the endpoints. The route is 55 + 5 = 60, starting at D and finishing at E, or the other way round. M1 for leaving two odd nodes unpaired, A1 for the cheapest pairing of 5, A1 for 60, B1 for the two endpoints.Explain why the pairings use shortest paths between odd nodes rather than single edges, and why repeating an edge between two even nodes never helps.
Worked answer
Two odd nodes may not be joined directly, and even when they are, a route through other nodes may be shorter. Repeating the edges of a shortest path raises the order of the two odd ends by one each and raises the intermediate nodes by two, leaving them even. Repeating an edge between two even nodes would make both odd, adding to the problem instead of solving it. B1 for a direct edge not always existing, B1 for a path through other nodes possibly being shorter, B1 for repeating an edge between even nodes making both odd.A network has vertices A to F and edges AB 7, AC 5, AE 8, BC 4, BD 7, CD 6, CE 3, CF 10, DE 5, DF 8, EF 5. Find the length of the shortest closed route that traverses every edge at least once, and state which edges are repeated.
Worked answer
Degrees: A 3, B 3, C 5, D 4, E 4, F 3. The odd vertices are A, B, C and F, and the edges total 68.
Shortest paths between them: AB = 7 along the edge; AC = 5; BC = 4; AF = 13 by A, C, E, F; BF = 12 by B, C, E, F; and CF = 8 by C, E, F, which beats the direct edge CF of 10.
Pairings: AB + CF = 7 + 8 = 15; AC + BF = 5 + 12 = 17; AF + BC = 13 + 4 = 17.
The cheapest is 15, so the shortest closed route has length 68 + 15 = 83, and the repeated edges are AB, CE and EF.
B1 for the four odd vertices, B1 for the total of 68, M1 for the shortest paths between odd vertices, A1 for the C to F path of 8, M1 for the three pairings, A1 for 15, A1 for 83, A1 for the repeated edges. The trap is the pair C and F. Taking the direct edge of 10 gives a pairing of 17 and a route of 85, and the two marks for the shortest paths are lost with it. Check every connection between odd vertices for a cheaper way round before pairing.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise route inspection one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.