8 Mrs Jones is a spy who has to visit six locations, \(P , Q , R , S , T\) and \(U\), to collect information. She starts at location \(Q\), and travels to each of the other locations, before returning to \(Q\). She wishes to keep her travelling time to a minimum. The diagram represents roads connecting different locations. The number on each edge represents the travelling time, in minutes, along that road.
\includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-16_524_866_612_587}

1. 1. Explain why the shortest time to travel from \(P\) to \(R\) is 40 minutes.
   2. Complete Table 1, on the opposite page, in which the entries are the shortest travelling times, in minutes, between pairs of locations.
2. 1. Use the nearest neighbour algorithm on Table 1, starting at \(Q\), to find an upper bound for the minimum travelling time for Mrs Jones's tour.
   2. Mrs Jones decides to follow the route given by the nearest neighbour algorithm. Write down her route, showing all the locations through which she passes.
3. By deleting \(Q\) from Table 1, find a lower bound for the travelling time for Mrs Jones's tour. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Table 1}

   	\(\boldsymbol { P }\)	\(Q\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(T\)	\(\boldsymbol { U }\)
   \(P\)	-	25
   \(Q\)	25	-	20	21	23	11
   \(\boldsymbol { R }\)		20	-
   \(\boldsymbol { S }\)		21		-
   \(T\)		23			-	12
   \(\boldsymbol { U }\)		11			12	-

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-18_2486_1714_221_153}