Bounds for the travelling salesman problemEdexcel International A Level Maths: Mind map

Exam questions on Bounds for the travelling salesman problem

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$.
   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
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$.
   Find the lower bound for the length of the shortest tour from deleting $V$, and explain why it is a lower bound.2 marks
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.
   Find the shortest distances between $A$ and $D$, between $B$ and $D$, and between $C$ and $E$.3 marks