Problem

The network in Figure 2 shows the distances, in miles, between ten towns, A, B, C, H, L, M, P, S, W and Y.

(a) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.

The table shows the shortest distances, in miles, between the ten towns.

(b) Use Prim’s algorithm on the table, starting at A, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.

(c) State the weight of the minimum spanning tree found in (b).

Sharon needs to visit all of the towns, starting and finishing in the same town, and wishes to minimise the total distance she travels.

(d) Use your answer to (c) to calculate an initial upper bound for the length of Sharon’s route.

(e) Use the nearest neighbour algorithm on the table, starting at W, to find an upper bound for the length of Sharon’s route. Write down the route which gives this upper bound.

Using the nearest neighbour algorithm, starting at Y, an upper bound of length 212 miles was found.

(f) State the best upper bound that can be obtained by using this information and your answers from (d) and (e). Give the reason for your answer.

(g) By deleting W and all of its arcs, find a lower bound for the length of Sharon’s route.

Sharon decides to take the route found in (e).

(h) Interpret this route in terms of the actual towns visited.