4. This question should be answered on the sheet provided.
A travelling salesman problem relates to the network represented by the following table of distances in kilometres. You may assume that the network satisfies the triangle inequality.
| A | B | \(C\) | D | \(E\) | \(F\) | G | \(H\) |
| A | - | 85 | 59 | 31 | 47 | 52 | 74 | 41 |
| B | 85 | - | 104 | 73 | 51 | 68 | 43 | 55 |
| C | 59 | 104 | - | 54 | 62 | 88 | 61 | 45 |
| D | 31 | 73 | 54 | - | 40 | 59 | 65 | 78 |
| E | 47 | 51 | 62 | 40 | - | 56 | 71 | 68 |
| \(F\) | 52 | 68 | 88 | 59 | 56 | - | 53 | 49 |
| G | 74 | 43 | 61 | 65 | 71 | 53 | - | 63 |
| H | 41 | 55 | 45 | 78 | 68 | 49 | 63 | - |
Showing your method clearly, use
- the nearest neighbour algorithm, beginning with \(A\),
- Prim's algorithm with \(H\) deleted,
to show that the minimum distance travelled, \(d \mathrm {~km}\), satisfies the inequality \(357 \leq d \leq 371\).
(11 marks)