Route inspection and travelling salespersonAQA A-Level Further Maths: Subtopic test

1. 1
   A network has six nodes $A$ to $F$. The arcs and their weights, in km, are $AB$ 6, $AC$ 5, $BC$ 4, $BD$ 7, $CD$ 3, $CE$ 8, $DE$ 6, $DF$ 9 and $EF$ 5. The total weight of all the arcs is 53 km.

   (a)

   Which nodes have odd degree?

   [1 mark]

   • A$B$ and $C$
   • B$B$ and $E$
   • C$A$ and $F$
   • D$C$ and $D$

   (b)

   What is the length of the shortest closed route that traverses every arc at least once?

   [1 mark]

   • A$53$ km
   • B$66$ km
   • C$65$ km
   • D$12$ km

   (c)

   The route may now start and finish at different nodes. State where it should start and finish and the length of the shortest such route that traverses every arc at least once.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A van starts at depot $A$, must visit each of depots $B$, $C$, $D$ and $E$ exactly once and return to $A$. The distances in km between each pair of depots are $AB$ 8, $AC$ 5, $AD$ 6, $AE$ 14, $BC$ 11, $BD$ 9, $BE$ 4, $CD$ 12, $CE$ 13 and $DE$ 15.

   (a)

   The nearest neighbour algorithm is applied starting at $A$. What is the length of the tour it produces?

   [1 mark]

   • A$36$ km
   • B$37$ km
   • C$43$ km
   • D$41$ km

   (b)

   Delete vertex $D$ and use the remaining vertices to find a lower bound for the length of the shortest tour. What is it?

   [1 mark]

   • A$32$ km
   • B$17$ km
   • C$23$ km
   • D$36$ km

   (c)

   Delete vertex $B$ instead, to find a lower bound. Use it, with your answer to part (a), to write down an interval for the length of the shortest tour.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A courier based at $A$ must deliver parcels to $B$, $C$ and $D$ and return to $A$, visiting each at least once. The roads, with lengths in km, are $AB$ 4, $BC$ 3, $CD$ 5, $DA$ 6 and $BD$ 9.

   (a)

   Show that the shortest distance from $B$ to $D$ is 8 km, and find the shortest distance from $A$ to $C$.

   [3 marks]

   (b)

   Using the shortest distances between $A$, $B$, $C$ and $D$, find the shortest route for the courier and state its length.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A council inspects every road in a village. The roads, with their lengths in km, are $AB$ 8, $AC$ 5, $AF$ 10, $BC$ 6, $BD$ 9, $CD$ 7, $CE$ 9, $DE$ 4, $DF$ 6 and $EF$ 7. The total length of all the roads is 71 km. The inspector must travel along every road at least once.

   (a)

   Find the length of the shortest route that starts and finishes at the same point and inspects every road. Show your working.

   [6 marks]

   (b)

   The inspector no longer needs to finish where they started. State where the inspector should start and finish and the length of the shortest route. Evaluate whether this is worthwhile if the inspector must be driven back to the starting point afterwards.

   [6 marks]

   Total for question 4: 12 marks

End of questions