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.