3. The table shows the least distances, in km, between five towns, \(A , B , C , D\) and \(E\).
Nassim wishes to find an interval which contains the solution to the travelling salesman problem for this network.
- Making your method clear, find an initial upper bound starting at \(A\) and using
- the minimum spanning tree method,
- the nearest neighbour algorithm.
| \(A\) | \(B\) | \(C\) | \(D\) | \(E\) |
| \(A\) | - | 153 | 98 | 124 | 115 |
| \(B\) | 153 | - | 74 | 131 | 149 |
| \(C\) | 98 | 74 | - | 82 | 103 |
| \(D\) | 124 | 131 | 82 | - | 134 |
| \(E\) | 115 | 149 | 103 | 134 | - |
- By deleting \(E\), find a lower bound.
- Using your answers to parts (a) and (b), state the smallest interval that Nassim could correctly write down.
(Total 12 marks)