1.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{d28d78c1-052d-4350-a7e3-284380e3bbab-2_703_958_351_552}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
The network in Figure 1 shows the distances, in km, between six towns, A, B, C, D, E and F. Mabintou needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.
- By inspection, complete the two copies of the table of least distances in your answer book.
- Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Mabintou's route. Write down the route which gives this upper bound.
- Starting by deleting A, and all of its arcs, find a lower bound for the route length.