MST with Parameter Constraint

3. The network represented by the table shows the least distances, in km, between seven theatres, A, \(\mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G . Jasmine needs to visit each theatre at least once starting and finishing at A. She wishes to minimise the total distance she travels. The least distance between A and B, is \(x \mathrm {~km}\), where \(21 < x < 27\)

1. Using Prim's algorithm, starting at A , obtain a minimum spanning tree for the network. You should list the arcs in the order in which you consider them.
2. Use your answer to (a) to determine an initial upper bound for the length of Jasmine's route.
3. Use the nearest neighbour algorithm, starting at A , to find a second upper bound for the length of the route. The nearest neighbour algorithm starting at F gives a route of \(\mathrm { F } - \mathrm { E } - \mathrm { B } - \mathrm { A } - \mathrm { G } - \mathrm { D } - \mathrm { C } - \mathrm { F }\).
4. State which of these two nearest neighbour routes gives the better upper bound. Give a reason for your answer. Starting by deleting A, and all of its arcs, a lower bound of 159 km for the length of the route is found.
5. Find \(x\), making your method clear.
6. Write down the smallest interval that you can be confident contains the optimal length of Jasmine's route. Give your answer as an inequality.

7. The network represented by the table shows the least distances, in km, between eight museums, A, B, C, D, E, F, G and H. A tourist wants to visit each museum at least once, starting and finishing at A. The tourist wishes to minimise the total distance travelled. The shortest distance between A and D is \(x \mathrm {~km}\) where \(32 \leqslant x \leqslant 35\)

1. Using Prim's algorithm, starting at A , obtain a minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
2. Use your answer to (a) to determine an initial upper bound for the length of the tourist's route.
3. Starting at A, use the nearest neighbour algorithm to find another upper bound for the length of the tourist's route. Write down the route that gives this upper bound. The nearest neighbour algorithm starting at E gives a route of $$\mathrm { E } - \mathrm { H } - \mathrm { A } - \mathrm { D } - \mathrm { G } - \mathrm { C } - \mathrm { B } - \mathrm { F } - \mathrm { E }$$
4. State which of these two nearest neighbour routes gives the better upper bound. Give reasons for your answer. Starting by deleting A, and all of its arcs, a lower bound of 235 km for the length of the route is found.
5. Determine the smallest interval that must contain the optimal length of the tourist's route. You must make your method and working clear.

7 Liam is taking part in a treasure hunt. There are five clues to be solved and they are at the points \(A , B , C , D\) and \(E\). The table shows the distances between pairs of points. All of the distances are functions of \(x\), where \(\boldsymbol { x }\) is an integer. Liam must travel to all five points, starting and finishing at \(A\).

1. The nearest point to \(A\) is \(C\).
   1. By considering \(A C\) and \(A B\), show that \(x < 10\).
   2. Find two other inequalities in \(x\).
2. The nearest neighbour algorithm, starting from \(A\), gives a unique minimum tour \(A C D E B A\).
   1. By considering the fact that Liam's tour visits \(D\) immediately after \(C\), find two further inequalities in \(x\).
   2. Find the value of the integer \(x\).
   3. Hence find the total distance travelled by Liam if he uses this tour.