3 The network below represents a system of roads. The vertices represent villages and the arcs represent the roads between the villages. The weights on the arcs represent travel times by bicycle between villages, in minutes.
\includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-02_531_1113_1304_516} Alf wants to cycle from his home at \(A\) to visit each of the other villages and return to \(A\) in the shortest possible time.

1. Which standard network problem does Alf need to solve to find the quickest tour through all the villages?
2. Apply the nearest neighbour method starting at \(A\) to find a tour through all the villages that starts and ends at \(A\). Calculate the journey time for this tour. What can you deduce from this about the shortest possible time for Alf's tour?
3. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex \(A\) and all the arcs that are directly joined to \(A\). Start building your tree at vertex \(B\). (You do not need to represent the network as a matrix.) Give the order in which vertices are added to your tree and draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Alf's journey time.
4. Write down a route for Alf that would take him 125 minutes.