The table shows the road distances in miles between five places in Great Britain. For example, the distance between Birmingham and Cardiff is 103 miles.

\begin{tabular}{c|c|c|c|c}
 & Ayr & & & \\
250 & & Birmingham & & \\
350 & 103 & & Cardiff & \\
235 & 104 & 209 & & Doncaster \\
446 & 157 & 121 & 261 & Exeter
\end{tabular}

\begin{enumerate}[label=(\roman*)]
\item Complete the network in the answer booklet to show this information. The vertices are labelled by using the initial letter of each place. [2]

\item List the ten arcs by increasing order of weight. Apply Kruskal's algorithm to the list. Any entries that are crossed out should still be legible. Draw the resulting minimum spanning tree and give its total weight. [4]
\end{enumerate}

A sixth vertex, F, is added to the network. The distances, in miles, between F and each of the other places are shown in the table below.

\begin{tabular}{|c|c|c|c|c|}
\hline
& A & B & C & D & E \\
\hline
Distance from F & 200 & 50 & 150 & 59 & 250 \\
\hline
\end{tabular}

\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{2}
\item Use the weight of the minimum spanning tree from part (ii) to find a lower bound for the length of the minimum tour (cycle) that visits every vertex of the extended network with six vertices. [2]

\item Apply the nearest neighbour method, starting from vertex A, to find an upper bound for the length of the minimum tour (cycle) through the six vertices. [2]

\item Use the two least weight arcs through A to form a least weight path of the form $SAT$, where $S$ and $T$ are two of $\{B, C, D, E, F\}$, and give the weight of this path. Similarly write down a least weight path of the form $UEV$, where $U$ and $V$ are two of $\{A, B, C, D, F\}$, and give the weight of this path. You should find that the two paths that you have written down use all six vertices.

Now find the least weight way in which the two paths can be joined together to form a cycle through all six vertices. Hence write down a tour through the six vertices that has total weight less than the upper bound. Write down the total weight of this tour. [8]
\end{enumerate}

\hfill \mbox{\textit{OCR D1 2012 Q5 [18]}}