2. This question should be answered on the sheet provided.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{726bca96-7f98-4ed5-b642-f5007a958c8b-03_492_862_301_502}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{figure}
Figure 1 shows a network in which the nodes represent five major rides in a theme park and the arcs represent paths between these rides. The numbers on the arcs give the length, in metres, of the paths.
- By inspection, add additional arcs to make a complete network showing the shortest distances between the rides.
(2 marks) - Use the nearest neighbour algorithm, starting at \(A\), and your complete network to find an upper bound to the length of a tour visiting each ride exactly once.
- Interpret the tour found in part (b) in terms of the original network.