Problem

Table 1 represents a network that shows the travel times, in minutes, between eight towns, A, B, C, D, E, F, G and H.

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

(b) State the weight of the minimum spanning tree.

Table 2 shows the travel times, in minutes, between town J and towns A, B, C, D, E, F, G and H.

The journey time between towns E and J is $x$ minutes where $x > 28$.

A salesperson needs to visit all of the nine towns, starting and finishing at J.

The salesperson wishes to minimise the total time spent travelling.

(c) Starting at J, use the nearest neighbour algorithm to find an upper bound for the duration of the salesperson’s route. Write down the route that gives this upper bound.

Using the nearest neighbour algorithm, starting at E, an upper bound of 291 minutes for the salesperson’s route was found.

(d) State the best upper bound that can be obtained by using this information and your answer to (c). Give the reason for your answer.

Starting by deleting J and all of its arcs, a lower bound of 264 minutes for the duration of the salesperson’s route was found.

(e) Determine the value of $x$. You must make your method and working clear.