Robinson Tuition
AS Decision Mathematics 1 · Edexcel 8FM0 · free Further Maths worksheet

Route inspection

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.

Worksheet PDFWorked solutions PDFAnswers PDF

The questions

1

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.

561489654ABCDEFDiagram NOT accurately drawn
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.

  1. 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.
  2. Find the length of the shortest possible route.
101279118613ABCDEFDiagram NOT accurately drawn
5 marks
Show answer
a) BC and DE b) 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.

  1. State, with a reason, whether the network is Eulerian, semi-Eulerian or neither.
  2. Ella wants to cycle along every lane exactly once. State where she must start and finish, and the length of her route.
  3. Instead, Ella must start and finish at P. Find the length of the shortest route that covers every lane at least once.
7965114812103PQRSTUDiagram NOT accurately drawn
5 marks
Show answer
a) Semi-Eulerian: exactly two vertices, T and U, have odd degree b) Start at T, finish at U (or the reverse); 75 km c) 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.

  1. Find the total length of the corridors.
  2. Use the route inspection algorithm to find the corridors that will be travelled twice.
  3. Find the length of the cleaner's shortest route.
129108713611514ABCDEFGDiagram NOT accurately drawn
6 marks
Show answer
a) 95 m b) BD, CE, EF c) 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.

  1. 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.

  1. State where the lorry should start and finish so that its route is as short as possible, and find the length of this route.
18152124161912101413ABCDEFGDiagram NOT accurately drawn
7 marks
Show answer
a) 206 hundred metres b) 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.

BCDG
B−150410810
C150−550700
D410550−400
G810700400−
  1. Explain why the vertices in the table were chosen.
  2. Use the route inspection algorithm to find the length of the shortest inspection route. State the pipes that are inspected twice.
320280150410360190230270340200260170ABCDEFGHDiagram NOT accurately drawn
6 marks
Show answer
a) B, C, D, G are the vertices of odd degree b) 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.

  1. Explain why the ranger can check every footpath without walking any path twice, and state the length of her route.
  2. State how many times her route passes through D.

Footpath CD is closed and no longer needs checking, and it cannot be used.

  1. Find the length of the shortest route that checks every remaining footpath, starting and finishing at A.
685741296113108ABCDEFGDiagram NOT accurately drawn
7 marks
Show answer
a) All vertices have even degree (Eulerian); 89 km b) 2 times c) 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.

  1. Use the route inspection algorithm to find the length of the shortest route.
  2. State a possible route.
  3. State the number of times your route visits D, not counting the start or finish.
4635748710ABCDEFDiagram NOT accurately drawn
7 marks
Show answer
a) 69 km b) For example ABCDBDFCEFDA c) 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.

  1. 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.

  1. 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.
231914282516182130ABCDEFDiagram NOT accurately drawn
7 marks
Show answer
a) 235 m; CE and DE b) 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.

  1. Write down, in terms of x, the total length of the roads.
  2. Find the value of x. You must consider every pairing of the odd vertices.
1513119x8101712ABCDEFDiagram NOT accurately drawn
8 marks
Show answer
a) 95 + x b) 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.

  1. Use the route inspection algorithm to find the length of the shortest route. State the paths that are travelled twice.
  2. 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.

  1. State the start and finish that give the shortest route, and the length of that route.
0.80.60.50.41.21.01.10.70.60.91.30.8ABCDEFGHDiagram NOT accurately drawn
9 marks
Show answer
a) 12.4 km; BE and GH b) 37 minutes c) 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.

  1. 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.

  1. Find where she should finish to make her route as short as possible, and the length of this route.
  2. State which roads she drives along twice in part (b).
  3. Explain why she would not finish at an even vertex.
1411910128131520167ABCDEFGHDiagram NOT accurately drawn
10 marks
Show answer
a) 174 miles b) Finish at E; 155 miles c) CF d) 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.

All AS Decision Mathematics 1 topics