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)