3. The table below represents a complete network that shows the least costs of travelling between eight cities, A, B, C, D, E, F, G and H.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
 & A & B & C & D & E & F & G & H \\
\hline
A & - & 36 & 38 & 40 & 23 & 39 & 38 & 35 \\
\hline
B & 36 & - & 35 & 36 & 35 & 34 & 41 & 38 \\
\hline
C & 38 & 35 & - & 39 & 25 & 32 & 40 & 40 \\
\hline
D & 40 & 36 & 39 & - & 37 & 37 & 26 & 33 \\
\hline
E & 23 & 35 & 25 & 37 & - & 42 & 24 & 43 \\
\hline
F & 39 & 34 & 32 & 37 & 42 & - & 45 & 38 \\
\hline
G & 38 & 41 & 40 & 26 & 24 & 45 & - & 40 \\
\hline
H & 35 & 38 & 40 & 33 & 43 & 38 & 40 & - \\
\hline
\end{tabular}
\end{center}

Srinjoy must visit each city at least once. He will start and finish at A and wishes to minimise his total cost.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form the tree in the order in which you select them.
\item State the weight of the minimum spanning tree.
\item Use your answer to (b) to help you calculate an initial upper bound for the total cost of Srinjoy's route.
\item Show that there are two nearest neighbour routes that start from A. You must make the routes and their corresponding costs clear.
\item State the best upper bound that can be obtained by using your answers to (c) and (d).
\item Starting by deleting A and all of its arcs, find a lower bound for the total cost of Srinjoy's route. You must make your method and working clear.
\item Use your results to write down the smallest interval that must contain the optimal cost of Srinjoy's route.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2021 Q3 [15]}}