7 The diagram shows the locations of some schools. The number on each edge shows the distance, in miles, between pairs of schools.
\includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-14_1031_1231_428_392} Sam, an adviser, intends to travel from one school to the next until he has visited all of the schools, before returning to his starting school. The shortest distances for Sam to travel between some of the schools are shown in Table 1 opposite.

1. Complete Table 1.
2. 1. On the completed Table 1, use the nearest neighbour algorithm, starting from \(B\), to find an upper bound for the length of Sam's tour.
   2. Write down Sam's actual route if he were to follow the tour corresponding to the answer in part (b)(i).
   3. Using the nearest neighbour algorithm, starting from each of the other vertices in turn, the following upper bounds for the length of Sam's tour were obtained: 77, 77, 77, 76, 77 and 76. Write down the best upper bound. 7
3. 1. On Table 2 below, showing the order in which you select the edges, use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the schools \(A , B , C\), \(D , F\) and \(G\).
   2. Hence find a lower bound for the length of Sam's minimum tour.
   3. By deleting each of the other vertices in turn, the following lower bounds for the length of a minimum tour were found: \(50,48,52,51,56\) and 64 . Write down the best lower bound.
4. Given that the length of a minimum tour is \(T\) miles, use your answers to parts (b) and (c) to write down the smallest interval within which you know \(T\) must lie.
   (2 marks) \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Table 2}

   	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { F }\)	G
   A	-	2	6	4	16	27
   \(\boldsymbol { B }\)	2	-	8	3	15	26
   \(\boldsymbol { C }\)	6	8	-	10	22	32
   \(\boldsymbol { D }\)	4	3	10	-	12	23
   \(\boldsymbol { F }\)	16	15	22	12	-	20
   G	27	26	32	23	20	-

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-17_2486_1714_221_153}