7.
\includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-3_738_1052_466_516} The network in the diagram above shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.

1. Obtain a minimum spanning tree for the network using Kruskal's algorithm, stating the order in which you select the arcs.
2. Use your answer to part (a) to determine an initial upper bound for the length of the route.
3. Starting from your initial upper bound use short cuts to find an upper bound, which is below 630 km . State the corresponding route.
4. Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.
5. By deleting C, and all of its arcs, find a lower bound for the length of the route.
6. Use your results to write down the smallest interval which you are confident contains the optimal length of the route.
   (2) (Total 16 marks)