2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.
| A | B | C | D | E | F | G | H | J |
| A | - | 50 | 59 | 26 | 50 | 40 | 87 | 63 | 59 |
| B | 50 | - | 28 | 61 | 79 | 63 | 45 | 64 | 48 |
| C | 59 | 28 | - | 33 | 57 | 35 | 70 | 36 | 45 |
| D | 26 | 61 | 33 | - | 24 | 64 | 71 | 37 | 33 |
| E | 50 | 79 | 57 | 24 | - | 40 | 64 | 30 | 31 |
| F | 40 | 63 | 35 | 64 | 40 | - | 47 | 70 | 71 |
| G | 87 | 45 | 70 | 71 | 64 | 47 | - | 34 | 67 |
| H | 63 | 64 | 36 | 37 | 30 | 70 | 34 | - | 33 |
| J | 59 | 48 | 45 | 33 | 31 | 71 | 67 | 33 | - |
- Use Prim's algorithm, starting at D , to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.
- State the weight of the minimum spanning tree found in part (a).
- Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.
A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.
- Use your answer to part (b) to calculate an initial upper bound for the length of the historian's route.
- Use the nearest neighbour algorithm, starting at D , to find an upper bound for the length of the historian's route.
- Write down the route which gives this upper bound.
Using the nearest neighbour algorithm, starting at F , an upper bound of length 352 miles was found.
- State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer.
- By deleting A and all of its arcs, find a lower bound for the length of the historian's route.
(2)
By deleting J and all of its arcs, a lower bound of length 274 miles was found. - State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer.