State Best Bounds Interval

5 [Answer this question on the insert provided.] \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-3_659_1002_324_609} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the shortest distances in kilometres.

1. The diagram on the insert shows the result of deleting vertex \(F\) and all the arcs joined to \(F\). Show that a lower bound for the length of the travelling salesperson problem on the original network is 38 km . The corresponding lower bounds by deleting each of the other vertices are: $$A : 40 \mathrm {~km} , \quad B : 39 \mathrm {~km} , \quad C : 35 \mathrm {~km} , \quad D : 37 \mathrm {~km} , \quad E : 35 \mathrm {~km} \text {. }$$ The route \(A - B - C - D - E - F - A\) has length 47 km .
2. Using only this information, what are the best upper and lower bounds for the length of the solution to the travelling salesperson problem on the network?
3. By considering the orders in which vertices \(C , D\) and \(E\) can be visited, find the best upper bound given by a route of the form \(A - B - \ldots - F - A\).

7. \includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-3_738_1052_466_516} The network in the diagram above shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.

1. Obtain a minimum spanning tree for the network using Kruskal's algorithm, stating the order in which you select the arcs.
2. Use your answer to part (a) to determine an initial upper bound for the length of the route.
3. Starting from your initial upper bound use short cuts to find an upper bound, which is below 630 km . State the corresponding route.
4. Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.
5. By deleting C, and all of its arcs, find a lower bound for the length of the route.
6. Use your results to write down the smallest interval which you are confident contains the optimal length of the route.
   (2) (Total 16 marks)

1. The table above shows the least distances, in km, between six cities, A, B, C, D, E and F. Mohsen needs to visit each city, starting and finishing at A , and wishes to minimise the total distance he will travel.

1. Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Mohsen's route. You must state your route and its length.
2. Starting by deleting A and all of its arcs, find a lower bound for the length of Mohsen's route.
3. Use your answers from (a) and (b) to write down the smallest interval that you can be confident contains the optimal length of the route.

The table shows the least distances, in km, between five towns, \(A\), \(B\), \(C\), \(D\) and \(E\). Nassim wishes to find an interval which contains the solution to the travelling salesman problem for this network.

1. Making your method clear, find an initial upper bound starting at \(A\) and using
   1. the minimum spanning tree method, [4]
   2. the nearest neighbour algorithm. [3]
2. By deleting \(E\), find a lower bound. [4]
3. Using your answers to parts (a) and (b), state the smallest interval that Nassim could correctly write down. [1]

(Total 12 marks)