- The table below shows the least costs, in pounds, of travelling between six cities, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .
| A | B | C | D | E | F |
| A | - | 36 | 18 | 28 | 24 | 22 |
| B | 36 | - | 54 | 22 | 20 | 27 |
| C | 18 | 54 | - | 42 | 27 | 24 |
| D | 28 | 22 | 42 | - | 20 | 30 |
| E | 24 | 20 | 27 | 20 | - | 13 |
| F | 22 | 27 | 24 | 30 | 13 | - |
Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.
- Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.
(2) - Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
(1) - Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.
- State the best upper bound from your answers to (b) and (c).
- Starting by deleting A , and all of its arcs, find a lower bound for the route length.