1.
| A | B | C | D | E | F |
| A | - | 83 | 75 | 82 | 69 | 97 |
| B | 83 | - | 94 | 103 | 77 | 109 |
| C | 75 | 94 | - | 97 | 120 | 115 |
| D | 82 | 103 | 97 | - | 105 | 125 |
| E | 69 | 77 | 120 | 105 | - | 88 |
| F | 97 | 109 | 115 | 125 | 88 | - |
The table above shows the least distances, in km , between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .
- Starting at A, and making your working clear, find an initial upper bound for the travelling salesperson problem for this network, using
- the minimum spanning tree method,
- the nearest neighbour algorithm.
(5)
By deleting A, and all of its arcs, a lower bound for the travelling salesperson problem for this network is found to be 500 km .
By deleting B, and all of its arcs, the corresponding lower bound is found to be 474 km .
- Using the results from (a) and the given lower bounds, write down the smallest interval that you can be confident contains the solution to the travelling salesperson problem for this network.
(2)