7.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
 & A & B & C & D & E & F & G & H \\
\hline
A & - & 38 & 37 & $x$ & 37 & 42 & 41 & 27 \\
\hline
B & 38 & - & 26 & 32 & 33 & 38 & 37 & 34 \\
\hline
C & 37 & 26 & - & 39 & 38 & 39 & 30 & 39 \\
\hline
D & $x$ & 32 & 39 & - & 37 & 36 & 29 & 36 \\
\hline
E & 37 & 33 & 38 & 37 & - & 32 & 33 & 30 \\
\hline
F & 42 & 38 & 39 & 36 & 32 & - & 31 & 28 \\
\hline
G & 41 & 37 & 30 & 29 & 33 & 31 & - & 33 \\
\hline
H & 27 & 34 & 39 & 36 & 30 & 28 & 33 & - \\
\hline
\end{tabular}
\end{center}

The network represented by the table shows the least distances, in km, between eight museums, A, B, C, D, E, F, G and H.

A tourist wants to visit each museum at least once, starting and finishing at A. The tourist wishes to minimise the total distance travelled. The shortest distance between A and D is $x \mathrm {~km}$ where $32 \leqslant x \leqslant 35$
\begin{enumerate}[label=(\alph*)]
\item Using Prim's algorithm, starting at A , obtain a minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
\item Use your answer to (a) to determine an initial upper bound for the length of the tourist's route.
\item Starting at A, use the nearest neighbour algorithm to find another upper bound for the length of the tourist's route. Write down the route that gives this upper bound.

The nearest neighbour algorithm starting at E gives a route of

$$\mathrm { E } - \mathrm { H } - \mathrm { A } - \mathrm { D } - \mathrm { G } - \mathrm { C } - \mathrm { B } - \mathrm { F } - \mathrm { E }$$
\item State which of these two nearest neighbour routes gives the better upper bound.

Give reasons for your answer.

Starting by deleting A, and all of its arcs, a lower bound of 235 km for the length of the route is found.
\item Determine the smallest interval that must contain the optimal length of the tourist's route. You must make your method and working clear.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2023 Q7 [12]}}