Route inspection and travelling salespersonAQA A-Level Further Maths: Mind map

Exam questions on Route inspection and travelling salesperson

1. A network has six nodes $A$ to $F$. The arcs and their weights, in km, are $AB$ 6, $AC$ 5, $BC$ 4, $BD$ 7, $CD$ 3, $CE$ 8, $DE$ 6, $DF$ 9 and $EF$ 5. The total weight of all the arcs is 53 km.
   The route may now start and finish at different nodes. State where it should start and finish and the length of the shortest such route that traverses every arc at least once.2 marks
2. A van starts at depot $A$, must visit each of depots $B$, $C$, $D$ and $E$ exactly once and return to $A$. The distances in km between each pair of depots are $AB$ 8, $AC$ 5, $AD$ 6, $AE$ 14, $BC$ 11, $BD$ 9, $BE$ 4, $CD$ 12, $CE$ 13 and $DE$ 15.
   Delete vertex $B$ instead, to find a lower bound. Use it, with your answer to part (a), to write down an interval for the length of the shortest tour.2 marks
3. A courier based at $A$ must deliver parcels to $B$, $C$ and $D$ and return to $A$, visiting each at least once. The roads, with lengths in km, are $AB$ 4, $BC$ 3, $CD$ 5, $DA$ 6 and $BD$ 9.
   Show that the shortest distance from $B$ to $D$ is 8 km, and find the shortest distance from $A$ to $C$.3 marks