Bounds for the travelling salesman problemEdexcel International A Level Maths: Subtopic test

1. 1
   A complete network has five vertices $P$, $Q$, $R$, $S$ and $T$, with lengths $PQ=14$, $PR=10$, $PS=17$, $PT=9$, $QR=11$, $QS=8$, $QT=15$, $RS=12$, $RT=13$ and $ST=16$.

   (a)

   The nearest neighbour algorithm is applied starting at $Q$. Which tour is produced?

   [1 mark]

   • A$Q$-$R$-$P$-$T$-$S$-$Q$
   • B$Q$-$S$-$P$-$T$-$R$-$Q$
   • C$Q$-$P$-$T$-$R$-$S$-$Q$
   • D$Q$-$S$-$R$-$P$-$T$-$Q$

   (b)

   The tour from $Q$ in part (a) has length $54$. Which statement about the travelling salesman problem is correct?

   [1 mark]

   • AThe shortest tour has length exactly $54$
   • BThe shortest tour has length at most $54$
   • CThe shortest tour has length at least $54$
   • DEvery starting vertex gives a tour of length $54$

   (c)

   Apply the nearest neighbour algorithm starting at $P$. Write down the tour and its length, and state what this tells you about the shortest tour.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A complete network has five depots $V$, $W$, $X$, $Y$ and $Z$, with lengths $VW=11$, $VX=7$, $VY=9$, $VZ=14$, $WX=6$, $WY=13$, $WZ=10$, $XY=8$, $XZ=12$ and $YZ=15$. A lower bound for the travelling salesman problem is found by deleting vertex $V$.

   (a)

   What is the total length of a minimum spanning tree of the network with $V$ deleted?

   [1 mark]

   • A$24$
   • B$26$
   • C$34$
   • D$40$

   (b)

   Which two arcs at $V$ are added to the minimum spanning tree to form the lower bound?

   [1 mark]

   • A$VZ$ and $VW$
   • B$VX$ and $VW$
   • C$VX$ and $VY$
   • D$VY$ and $VZ$

   (c)

   Find the lower bound for the length of the shortest tour from deleting $V$, and explain why it is a lower bound.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A delivery firm has five depots $A$ to $E$. The only direct roads and their lengths in km are $AB=7$, $BC=5$, $CD=6$, $DE=4$ and $BE=9$. A driver must visit every depot and return to the start, and may pass through a depot more than once.

   (a)

   Find the shortest distances between $A$ and $D$, between $B$ and $D$, and between $C$ and $E$.

   [3 marks]

   (b)

   The shortest distances are $AB=7$, $AC=12$, $AD=18$, $AE=16$, $BC=5$, $BD=11$, $BE=9$, $CD=6$, $CE=10$ and $DE=4$. Apply the nearest neighbour algorithm to this complete network starting at $A$, to find an upper bound. Give the route that the driver takes in the original network.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A complete network has five vertices $A$, $B$, $C$, $D$ and $E$, with lengths $AB=12$, $AC=9$, $AD=15$, $AE=7$, $BC=8$, $BD=11$, $BE=14$, $CD=10$, $CE=13$ and $DE=6$.

   (a)

   (i) Use Kruskal's algorithm to find a minimum spanning tree and its weight.
   (ii) Hence find an upper bound by walking around the tree, and use shortcuts to improve this bound.

   [6 marks]

   (b)

   Find a lower bound by deleting $B$. Hence show that the shortest tour has length $41$.

   [6 marks]

   Total for question 4: 12 marks

End of questions