Fred delivers bread to five shops, $A$, $B$, $C$, $D$ and $E$. Fred starts his deliveries at shop $B$, and travels to each of the other shops once before returning to shop $B$. Fred wishes to keep his travelling time to a minimum.

The table shows the travelling times, in minutes, between the shops.

$$\begin{array}{c|ccccc}
 & A & B & C & D & E \\
\hline
A & - & 3 & 11 & 15 & 5 \\
B & 3 & - & 18 & 12 & 4 \\
C & 11 & 18 & - & 5 & 16 \\
D & 15 & 12 & 5 & - & 10 \\
E & 5 & 4 & 16 & 10 & -
\end{array}$$

\begin{enumerate}[label=(\alph*)]
\item Find the travelling time for the tour $BACDEB$. [1]
\item Use the nearest neighbour algorithm, starting at $B$, to find another upper bound for the travelling time for Fred's tour. [3]
\item By deleting $C$, find a lower bound for the travelling time for Fred's tour. [4]
\item Sketch a network showing the edges that give you the lower bound in part (c) and comment on its significance. [2]
\end{enumerate}

\hfill \mbox{\textit{AQA D1 2011 Q7 [10]}}