1.

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 1}
  \includegraphics[alt={},max width=\textwidth]{c4c64221-0373-4be9-abe3-5ff281922cdb-01_675_1052_378_485}
\end{center}
\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 .
\begin{enumerate}[label=(\alph*)]
\item 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.
\item 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)
\item Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.\\
(1)
\item 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)
\end{enumerate}

\hfill \mbox{\textit{Edexcel D2 2002 Q1 [8]}}