5 [Figure 2, printed on the insert, is provided for use in this question.]
\begin{enumerate}[label=(\alph*)]
\item Gill is solving a travelling salesperson problem.
\begin{enumerate}[label=(\roman*)]
\item She finds the following upper bounds: 7.5, 8, 7, 7.5, 8.5.

Write down the best upper bound.
\item She finds the following lower bounds: $6.5,7,6.5,5,7$.

Write down the best lower bound.
\end{enumerate}\item George is travelling by plane to a number of cities. He is to start at $F$ and visit each of the other cities at least once before returning to $F$.

The diagram shows the times of flights, in hours, between cities. Where no time is shown, there is no direct flight available.\\
\includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-05_936_826_1162_589}
\begin{enumerate}[label=(\roman*)]
\item Complete Figure 2 to show the minimum times to travel between all pairs of cities.
\item Find an upper bound for the minimum total flying time by using the route FTPOMF.
\item Using the nearest neighbour algorithm starting from $F$, find an upper bound for the minimum total flying time.
\item By deleting $F$, find a lower bound for the minimum total flying time.
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{AQA D1 2006 Q5 [18]}}