The route inspection problemEdexcel International A Level Maths: Mind map

Exam questions on The route inspection problem

1. A street cleaner must travel along every street in a small town, starting and finishing at the same junction. The junctions are $A$, $B$, $C$, $D$ and $E$, and the streets and their lengths in hundreds of metres are $AB=5$, $AC=8$, $BC=4$, $BD=7$, $CD=6$, $CE=9$ and $DE=3$.
   Find the length of the shortest route that the cleaner can take.2 marks
2. A network has four vertices $W$, $X$, $Y$ and $Z$, and every pair of vertices is joined by an arc. The lengths are $WX=6$, $WY=9$, $WZ=8$, $XY=7$, $XZ=10$ and $YZ=5$. A route must traverse every arc at least once, starting and finishing at $W$.
   Find the length of the shortest route.2 marks
3. A gritting lorry must travel along every road in a village at least once, starting and finishing at the depot $A$. The junctions are $A$, $B$, $C$, $D$ and $E$, and the roads and their lengths in km are $AB=2$, $AC=3$, $BC=13$, $BD=8$, $CD=5$, $CE=4$, $DE=11$ and $AE=10$.
   List the odd vertices. Find the three ways of pairing them, and the total length of the shortest connections for each pairing.3 marks