AI HL · AHL 1
0 of 43 skills done
The Chinese postman problem
AHL 1.10
The postman walks every edge and returns to the start. Find the odd vertices, then choose which edges to walk twice. Press Next to move on.
Repeat which edges? ()
A park keeper must walk along every path in the park, starting and finishing at A. The graph shows the paths and their lengths in metres. Find the length of the shortest route and state which paths are walked twice.
Have a go first. Then open the working one line at a time.
A 2, B 3, C 2, F 2, E 3, D 2
Odd vertices: B and E. Two odd vertices: repeat the shortest path between them.
B–C–D–E = 9; B–E = 10; B–A–F–E = 32
The shortest path from B to E is B–C–D–E, length 9.
Repeat BC (2), CD (3), DE (4)
These edges are walked twice.
51 + 9 = 60
Total weight of the edges, 12 + 2 + 3 + 4 + 13 + 7 + 10 = 51, plus the repeated path.
A delivery rider must travel along every road shown, starting and finishing at A. The numbers are lengths in km. Find the length of the shortest route and write down a route that has this length.
Have a go first. Then open the working one line at a time.
A 4, B 2, C 3, D 3, E 2
Odd vertices: C and D. Two odd vertices: repeat the shortest path between them.
C–A–D = 5; C–D = 8; C–B–A–D = 15; C–A–E–D = 21
The shortest path from C to D is C–A–D, length 5.
7 edges + 2 repeated = 9 edges walked
Use each edge once and the repeated edges CA (2), AD (3) a second time.
A–B–C–A–C–D–A–D–E–A
This is one possible route. Others of the same length also work.
44 + 5 = 49
Total weight 44, plus the repeated path 5.
A council gritter must drive along every road shown, then return to its start. The numbers are lengths in km. Find the length of the shortest route and state which roads are driven twice.
Have a go first. Then open the working one line at a time.
A 2, B 3, C 3, D 3, E 3, F 2
Four odd vertices: B, C, D, E. Pair them up in the three possible ways.
B–C (13) and D–E (2): total 15; B–D (7) and C–E (10): total 17; B–D–E (9) and C–E–D (12): total 21
For each pair, use the shortest path between them. Compare the three totals.
Repeat BC (13), DE (2)
The smallest total is 15, so these edges are walked twice.
66 + 15 = 81
Total weight of the edges, 66, plus the repeated edges.
A surveyor must inspect every path in the garden shown and return to the start. The numbers are lengths in metres. Compare the three pairings of the odd vertices and find the length of the shortest route.
Have a go first. Then open the working one line at a time.
A 3, B 3, C 3, D 3, E 2, F 2
Four odd vertices: A, B, C, D. Pair them up in the three possible ways.
A–B (14) and C–D (3): total 17; A–D–C (12) and B–C–D (14): total 26; A–D (9) and B–C (11): total 20
For each pair, use the shortest path between them. Compare the three totals.
Repeat AB (14), CD (3)
The smallest total is 17, so these edges are walked twice.
68 + 17 = 85
Total weight of the edges, 68, plus the repeated edges.
A runner plans a training route that covers every path of a nature reserve at least once. The graph shows the paths between six viewpoints, with lengths in km. The route must start at the car park A and finish at the cafe B. Find the length of the shortest route.
Have a go first. Then open the working one line at a time.
A 3, B 3, C 2, D 3, E 2, F 3
Odd vertices: A, B, D, F. The route may finish at a different vertex, so A and B can stay odd.
Only D and F must be made even
Repeat the shortest path between D and F. A path with more edges can be shorter than the direct edge.
D–E–F = 11; D–F = 16; D–B–C–A–F = 24
The shortest path from D to F is D–E–F, length 11. The direct edge is 16.
Total weight 63 + 11 = 74
Total weight of all the edges, plus the repeated path.
AB + DF = 7 + 11 = 18; AD + BF = 17 + 14 = 31; AF + BD = 7 + 10 = 17; smallest 17, route 63 + 17 = 80
Returning to A needs all four odd vertices fixed, so the route is 6 km longer.