The travelling salesman problemEdexcel International A Level Maths: Mind map

Exam questions on The travelling salesman problem

1. A sales representative must visit four towns $P$, $Q$, $R$ and $S$, starting and finishing at $P$. Every pair of towns is joined by a direct road. The distances in km are $PQ=12$, $PR=15$, $PS=9$, $QR=8$, $QS=14$ and $RS=11$. Each town is to be visited exactly once.
   Find the length of the shortest tour for the classical problem.2 marks
2. A driver starts at a depot $H$, delivers to three shops $A$, $B$ and $C$, and returns to $H$. The only roads are $HA=5$, $HB=7$ and $HC=4$, with lengths in km. The driver may pass through a junction more than once.
   A fourth shop $D$ is added, joined only to $C$ by a road of length $3$ km. Find the length of the shortest route that visits all four shops and returns to $H$.2 marks
3. Four offices $W$, $X$, $Y$ and $Z$ are joined by a complete network of direct links. The lengths in km are $WX=20$, $WY=35$, $WZ=25$, $XY=15$, $XZ=30$ and $YZ=10$.
   Show that the triangle inequality is not satisfied by this network.3 marks