The Chinese postman problem with two or four odd vertices, pairing odd vertices and choosing the least pairing, length of the route and which edges are repeated, starting and finishing at different vertices.
12 original questions, 81 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.
The network below shows the lengths, in km, of the roads in a small housing estate in Swindon. The total length of the roads is 57 km.
A council officer must travel along every road at least once, starting and finishing at A. Use an appropriate algorithm to find the length of the shortest possible route, stating the roads that must be travelled twice.
4 marks
Show answer
Repeat BE and DE; length 70 km
2
The network below shows the lengths, in hundreds of metres, of the paths in a park in Glasgow. The total length of the paths is 76 hundred metres.
A park keeper must walk along every path at least once to check for damage, starting and finishing at A.
Use the route inspection algorithm to find which paths must be walked twice. You must make your method clear, considering every possible pairing of the odd vertices.
Find the length of the shortest possible route.
5 marks
Show answer
a) BC and DEb) 91 hundred metres
3
The network below shows the lengths, in km, of the cycle lanes in a town in Suffolk. The total length is 75 km.
State, with a reason, whether the network is Eulerian, semi-Eulerian or neither.
Ella wants to cycle along every lane exactly once. State where she must start and finish, and the length of her route.
Instead, Ella must start and finish at P. Find the length of the shortest route that covers every lane at least once.
5 marks
Show answer
a) Semi-Eulerian: exactly two vertices, T and U, have odd degreeb) Start at T, finish at U (or the reverse); 75 kmc) 85 km
4
The network below shows the lengths, in metres, of the corridors in a hospital wing. A cleaner must travel along every corridor at least once, starting and finishing at A.
Find the total length of the corridors.
Use the route inspection algorithm to find the corridors that will be travelled twice.
Find the length of the cleaner's shortest route.
6 marks
Show answer
a) 95 mb) BD, CE, EFc) 117 m
5
A road-sweeping lorry in Coventry must travel along every road in the network below at least once. The number on each arc is the length of the road in hundreds of metres, and the total length of the roads is 162 hundred metres.
Find the length of the shortest route that starts and finishes at the depot, A.
The lorry may instead start and finish at any two vertices.
State where the lorry should start and finish so that its route is as short as possible, and find the length of this route.
7 marks
Show answer
a) 206 hundred metresb) Start at C, finish at E (or the reverse); 183 hundred metres
6
The network below shows the lengths, in metres, of the pipes in a water treatment works. The total length is 3180 m. An engineer must inspect every pipe, starting and finishing at A.
The table shows the shortest distances, in metres, between some of the vertices.
B
C
D
G
B
−
150
410
810
C
150
−
550
700
D
410
550
−
400
G
810
700
400
−
Explain why the vertices in the table were chosen.
Use the route inspection algorithm to find the length of the shortest inspection route. State the pipes that are inspected twice.
6 marks
Show answer
a) B, C, D, G are the vertices of odd degreeb) 3730 m; BC, DF, FG
7
The network below shows the lengths, in km, of the footpaths that a ranger in the New Forest must check, starting and finishing at A. The total length is 89 km.
Explain why the ranger can check every footpath without walking any path twice, and state the length of her route.
State how many times her route passes through D.
Footpath CD is closed and no longer needs checking, and it cannot be used.
Find the length of the shortest route that checks every remaining footpath, starting and finishing at A.
7 marks
Show answer
a) All vertices have even degree (Eulerian); 89 kmb) 2 timesc) 97 km
8
The network below shows the lengths, in km, of the streets that a postal worker in Belfast must walk along, starting and finishing at the sorting office, A.
Use the route inspection algorithm to find the length of the shortest route.
State a possible route.
State the number of times your route visits D, not counting the start or finish.
7 marks
Show answer
a) 69 kmb) For example ABCDBDFCEFDAc) 3
9
The network below shows the lengths, in metres, of the aisles in a supermarket warehouse in Reading. The total length is 194 m. A security guard must patrol every aisle at least once, starting and finishing at A.
Find the length of the shortest patrol route, stating the aisles that are patrolled twice.
The manager plans to open a new aisle of length 35 m directly between C and D. The new aisle must also be patrolled.
Find the length of the shortest patrol route with the new aisle, and state whether the new aisle makes the patrol shorter or longer, and by how much.
7 marks
Show answer
a) 235 m; CE and DEb) 229 m; shorter by 6 m
10
The network below shows the lengths, in km, of the roads between six villages in Herefordshire. The length of road BE is x km, where 8 < x < 19
A gritting lorry must travel along every road at least once, starting and finishing at A. The shortest possible route has length 144 km.
Write down, in terms of x, the total length of the roads.
Find the value of x. You must consider every pairing of the odd vertices.
8 marks
Show answer
a) 95 + xb) x = 17
11
The network below shows the lengths, in km, of the paths in a university campus in Durham that must be gritted on an icy morning. The total length is 9.9 km. The gritter starts and finishes at its store, A, and must travel along every path at least once.
Use the route inspection algorithm to find the length of the shortest route. State the paths that are travelled twice.
The gritter travels at an average speed of 20 km/h. Find the time taken for the route, to the nearest minute.
The store moves, so that the gritter may now start and finish at any vertices.
State the start and finish that give the shortest route, and the length of that route.
9 marks
Show answer
a) 12.4 km; BE and GHb) 37 minutesc) B and G; 10.8 km
12
The network below shows the lengths, in miles, of the roads that a highways inspector in Somerset must drive along. The total length of the roads is 135 miles.
Find the length of the shortest route that covers every road and starts and finishes at D.
The inspector now lives at B. She will start at B but may finish at any vertex.
Find where she should finish to make her route as short as possible, and the length of this route.
State which roads she drives along twice in part (b).
Explain why she would not finish at an even vertex.
10 marks
Show answer
a) 174 milesb) Finish at E; 155 milesc) CFd) A route ends at an odd vertex unless every vertex is even; finishing at an even vertex means all four odd vertices must be paired, which is longer.
Your score
Answer the questions above and your score appears here.
Every question here is original and written by Robinson Tuition. It follows the Edexcel AS Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.