1.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{c4c64221-0373-4be9-abe3-5ff281922cdb-01_675_1052_378_485}
\end{figure}
Figure 1 shows a network of roads connecting six villages \(A , B , C , D , E\) and \(F\). The lengths of the roads are given in km .
- Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection.
The table can now be taken to represent a complete network.
- Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once.
(3) - Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
(1) - By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.
(2)