The Travelling Salesman problemEdexcel A-Level Further Maths: Subtopic test

1. 1
   A salesman must visit each of towns A, B, C, D and E once, starting and finishing at A. The distances in km between the towns are: AB 12, AC 10, AD 14, AE 8, BC 3, BD 7, BE 9, CD 6, CE 11 and DE 12.

   (a)

   Using the nearest neighbour algorithm starting at A, which town is visited immediately after E?

   [1 mark]

   • AC
   • BD
   • CE
   • DB

   (b)

   What is the weight of the minimum spanning tree for the five towns?

   [1 mark]

   • A26
   • B40
   • C24
   • D33

   (c)

   Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the shortest route.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A courier must visit depots A, B, C, D and E and return to the start. The only direct roads and their lengths in km are: AB 6, BC 4, CD 5, DE 3, AE 12, BD 11 and CE 10.

   (a)

   What is the least distance between depots A and D?

   [1 mark]

   • A17
   • B18
   • C15
   • D12

   (b)

   Which statement describes the practical Travelling Salesman problem?

   [1 mark]

   • AEvery vertex is visited exactly once and the network must be complete
   • BEvery vertex is visited at least once, and a vertex or arc may be used more than once
   • CThe route may leave out some vertices
   • DThe route does not have to return to its start

   (c)

   Find the least distance between B and D, and the least distance between C and E.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A delivery driver must visit five shops A, B, C, D and E, starting and finishing at A, and visiting each shop exactly once. The distances in km between the shops are: AB 15, AC 22, AD 25, AE 18, BC 10, BD 20, BE 12, CD 14, CE 16 and DE 9. These distances satisfy the triangle inequality.

   (a)

   Find a lower bound for the length of the shortest route by deleting shop A.

   [3 marks]

   (b)

   Use the nearest neighbour algorithm starting at A to find an upper bound, and hence write down an interval in which the length of the shortest route must lie.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   An engineer must inspect six sites A, B, C, D, E and F, visiting each site once and returning to the start. The distances in km between the sites are: AB 11, AC 14, AD 20, AE 17, AF 9, BC 8, BD 15, BE 13, BF 12, CD 10, CE 16, CF 18, DE 7, DF 19 and EF 12. These distances satisfy the triangle inequality.

   (a)

   (i) Use Kruskal's algorithm to find a minimum spanning tree for the six sites, and state its weight.
   (ii) Hence find an upper bound by doubling the weight of the tree.
   (iii) Show that a shortcut gives an improved upper bound, and state the route and its length.

   [6 marks]

   (b)

   By deleting site A, find a lower bound for the length of the shortest route. Use it, with your answer to (a), to decide whether the route of length 57 km is the shortest possible. Justify your answer.

   [6 marks]

   Total for question 4: 12 marks

End of questions