| P | Q | R | S | T | U | V | |
|---|---|---|---|---|---|---|---|
| P | – | 105 | 90 | 195 | 270 | 95 | 155 |
| Q | 105 | – | 195 | 295 | 370 | 190 | 255 |
| R | 90 | 195 | – | 110 | 185 | 180 | 245 |
| S | 195 | 295 | 110 | – | 75 | 115 | 170 |
| T | 270 | 370 | 185 | 75 | – | 180 | 245 |
| U | 95 | 190 | 180 | 115 | 180 | – | 65 |
| V | 155 | 255 | 245 | 170 | 245 | 65 | – |
The table shows the least distances, in metres, between seven signposts, P, Q, R, S, T, U and V. Aisha must visit each signpost to check that it has not been damaged. She needs to find a route which minimises the distance travelled, starting and finishing at P.
(a) Use Prim’s algorithm, starting at P, to obtain a minimum spanning tree for the network. You must clearly show the order in which you select arcs.
(b) Use the answer to part (a) to obtain an initial upper bound for the length of Aisha’s route.
(c) Use the nearest neighbour algorithm, starting at P, to find a second upper bound for the length of Aisha’s route. You should state both the route and its length.
(d) By deleting T and all of its arcs, and using the answer to part (a), obtain a lower bound for the length of Aisha’s route.