- [Maximum mark: 12]
A hygiene inspector lives in Town A and must visit restaurants in five towns (B–F), before returning to A. The inspector must not repeat any of the towns. The distances, in km, between the six towns are shown in the table.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 31 | 28 | 26 | 22 | 23 | |
| B | 31 | 25 | 20 | 27 | 25 | |
| C | 28 | 25 | 19 | 22 | 24 | |
| D | 26 | 20 | 19 | 21 | 22 | |
| E | 22 | 27 | 22 | 21 | 24 | |
| F | 23 | 25 | 24 | 22 | 24 |
(a) Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of the journey the inspector must take. State the order in which the towns are to be visited. [4]
(b) By deleting A, use Prim’s algorithm starting at B to find a lower bound for the length of the inspector’s journey. [5]
(c) By considering the minimum spanning tree found in part (b), determine whether the journey given by this lower bound is an achievable solution. [3]