5 This question uses the same network as question 4.\\
The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres.\\
\includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-5_680_1154_431_459}

Gus wants to hunt for the treasure. He assumes that the treasure is located at a vertex, but he does not know which one.
\begin{enumerate}[label=(\roman*)]
\item (a) Use the nearest neighbour method starting at $G$ to find an upper bound for the length of the shortest closed route through every vertex.\\
(b) Gus follows this route, but starting at $A$. Write down his route, starting and ending at $A$.
\item Use Prim's algorithm on the network, starting at $A$, to find a minimum spanning tree. You should write down the arcs in the order they are included, draw the tree and give its total weight (in units of 100 metres).
\item (a) Vertex $H$ and all arcs joined to $H$ are removed from the original network. Write down the weight of the minimum spanning tree for vertices $A , B , C , D , E , F$ and $G$ in the resulting reduced network.\\
(b) Use this minimum spanning tree for the reduced network to find a lower bound for the length of the shortest closed route through every vertex in the original network.
\item Find a route that passes through every vertex, starting and ending at $A$, that is longer than the lower bound from part (iii)(b) but shorter than the upper bound from part (i)(a). Give the length of your route, in metres.

Assume that Gus travels along paths at a rate of $x$ minutes for every 100 metres and that he spends $y$ minutes at each vertex hunting for the treasure. Gus starts by hunting for the treasure at $A$. He then follows the route from part (iv), starting and finishing at $A$ and hunting for the treasure at each vertex.

Unknown to Gus, the treasure is found before he gets to it, so he has to search at every vertex. Gus can take at most 2 hours from when he starts searching at $A$ to when he arrives back at $A$.
\item Use this information to write down a constraint on $x$ and $y$.

The treasure was at $H$ and was found 40 minutes after Gus started. This means that Gus takes more than 40 minutes to get to $H$.
\item Use this information to write down a second constraint on $x$ and $y$.
\end{enumerate}

\hfill \mbox{\textit{OCR D1 2014 Q5 [15]}}