Identify Best Lower Bound

6. The network in the figure above, shows the distances in km , along the roads between eight towns, A, B, C, D, E, F, G and H. Keith has a shop in each town and needs to visit each one. He wishes to travel a minimum distance and his route should start and finish at A . By deleting D, a lower bound for the length of the route was found to be 586 km .
By deleting F, a lower bound for the length of the route was found to be 590 km .

1. By deleting C, find another lower bound for the length of the route. State which is the best lower bound of the three, giving a reason for your answer.
2. By inspection complete the table of least distances. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(8)
   (8)
   (Total 13 marks)} \includegraphics[alt={},max width=\textwidth]{a5d69a77-c196-483c-a550-1a55363555af-3_780_889_1069_1078}
   \end{figure} (4) The table can now be taken to represent a complete network. The nearest neighbour algorithm was used to obtain upper bounds for the length of the route: Starting at D, an upper bound for the length of the route was found to be 838 km .
   Starting at F, an upper bound for the length of the route was found to be 707 km .
3. Starting at C , use the nearest neighbour algorithm to obtain another upper bound for the length of the route. State which is the best upper bound of the

   	A	B	C	D	E	F	G	H
   A	-	84	85	138	173		149	52
   B	84	-	130	77	126	213	222	136
   C	85	130	-	53	88	83	92
   D	138	77	53	-	49			190
   E	173	126	88	49	-	100	180	215
   F		213	83		100	-	163	115
   G	149	222	92		180	163	-	97
   H	52	136		190	215	115	97	-

   three, giving a reason for your answer.
   (4) (Total 13 marks)

4. \begin{figure}[h] \end{figure} The network in Figure 2 shows the distances, in km , of the cables between seven electricity relay stations \(A , B , C , D , E , F\) and \(G\). An inspector needs to visit each relay station. He wishes to travel a minimum distance, and his route must start and finish at the same station. By deleting C, a lower bound for the length of the route is found to be 129 km .

1. Find another lower bound for the length of the route by deleting \(F\). State which is the best lower bound of the two.
2. By inspection, complete the table of least distances. The table can now be taken to represent a complete network.
3. Using the nearest-neighbour algorithm, starting at \(F\), obtain an upper bound to the length of the route. State your route.

A student is trying to find the solution to the travelling salesperson problem for a network. They correctly find two lower bounds for the solution: 15 and 19 They also correctly find two upper bounds for the solution: 48 and 51 Based on the above information only, which of the following pairs give the best lower bound and best upper bound for the solution of this problem? Tick \((\checkmark)\) one box. [1 mark]

Best Lower Bound	Best Upper Bound
15	48	\(\square\)
15	51	\(\square\)
19	48	\(\square\)
19	51	\(\square\)