6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} A band is going on tour to play gigs in six towns, including their home town, \(A\). The network in Figure 1 shows the distances, in miles, between the various towns. The band must begin and end their tour at \(A\) and visit each of the other towns once, and they wish to keep the total distance travelled as small as possible.

1. By inspection, draw a complete network showing the shortest distances between the towns.
2. Use your complete network and the nearest neighbour algorithm, starting at \(A\), to find an upper bound for the total distance travelled.
3. 1. Use your complete network to obtain and draw a minimum spanning tree and hence obtain another upper bound for the total distance travelled.
   2. Improve this upper bound using two shortcuts to find an upper bound below 225 miles.
4. By deleting \(A\), find a lower bound for the total distance travelled.
5. State an interval of as small a width as possible within which \(d\), the minimum distance travelled, in miles, must lie. \section*{Please hand this sheet in for marking}

   Stage	Previous tournament	Current tournament
   \multirow[t]{3}{*}{1}	G	J K L
   	\(H\)	J K L
   	I	J K L
   \multirow[t]{3}{*}{2}	D	G H I
   	\(E\)	G H I
   	\(F\)	G H I
   \multirow[t]{3}{*}{3}	A	D E F
   	\(B\)	D E F
   	C	D E F
   4	None	A B C

   \section*{Please hand this sheet in for marking}
6. 
   \includegraphics[max width=\textwidth, alt={}, center]{073926c5-03cc-41d4-82bf-315740ead663-8_684_992_461_427}
7. \section*{Sheet for answering question 6 (cont.)}
8. 2. \(\_\_\_\_\)
10. \(\_\_\_\_\)