The Route Inspection (Chinese Postman) problemEdexcel A-Level Further Maths: Subtopic test

1. 1
   A network has vertices A, B, C, D and E. The arcs and their weights are: AB 5, AC 7, BC 4, BD 6, CD 3, CE 8 and DE 5.

   (a)

   Which vertices have odd degree?

   [1 mark]

   • AA and E
   • BB and D
   • CC only
   • DB, C and D

   (b)

   What is the total weight of all the arcs?

   [1 mark]

   • A32
   • B44
   • C38
   • D76

   (c)

   Find the length of the shortest route that starts and ends at A and uses every arc at least once.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A network has vertices A, B, C, D, E and F. The arcs and their weights are: AB 8, BC 6, CD 9, DE 7, EF 5, FA 10, BE 12 and CF 11.

   (a)

   The network has four odd vertices. In how many different ways can these four vertices be split into two pairs?

   [1 mark]

   • A3
   • B4
   • C6
   • D2

   (b)

   What is the least total weight that must be added by repeating arcs so that the network can be traversed from A and back to A?

   [1 mark]

   • A23
   • B33
   • C17
   • D11

   (c)

   State which arcs are repeated and find the length of the shortest route that starts and ends at A and uses every arc at least once.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A council must inspect every road in a village. The junctions are A, B, C, D, E and F and the road lengths in km are: AB 3, AC 5, BC 2, BD 7, CD 4, CE 7, DF 5 and EF 3. The inspector starts and finishes at junction A.

   (a)

   Find the length of the shortest inspection route.

   [3 marks]

   (b)

   A new road CF of length 3 km is built. Find the new length of the shortest inspection route.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A park warden must walk along every path in a nature reserve, starting and finishing at the car park A. The path junctions are A, B, C, D, E and F, and the path lengths, in hundreds of metres, are: AB 4, BC 7, CD 5, DE 6, EF 3, FA 8 and BE 20.

   (a)

   (i) Identify the odd vertices.
   (ii) Find the shortest path between the odd vertices.
   (iii) Hence find the length of the warden's shortest route and state which paths are walked twice.

   [6 marks]

   (b)

   A new path CE of length 4 is built. Find the new length of the shortest route and decide whether building the path shortens the warden's walk. Justify your answer.

   [6 marks]

   Total for question 4: 12 marks

End of questions