6. This question should be answered on the sheet provided.
A furniture company in Leeds is considering opening outlets in six other cities.
The table below shows the distances, in miles, between all seven cities.
| Leeds | Liverpool | Manchester | Newcastle | Nottingham | Oxford | York |
| Leeds | - | 71 | 40 | 96 | 71 | 165 | 28 |
| Liverpool | 71 | - | 31 | 155 | 92 | 155 | 93 |
| Manchester | 40 | 31 | - | 136 | 62 | 141 | 67 |
| Newcastle | 96 | 155 | 136 | - | 156 | 250 | 78 |
| Nottingham | 71 | 92 | 62 | 156 | - | 94 | 78 |
| Oxford | 165 | 155 | 141 | 250 | 94 | - | 172 |
| York | 28 | 93 | 67 | 78 | 78 | 172 | - |
- Starting with Leeds, obtain and draw a minimum spanning tree for this network of cities showing your method clearly.
(4 marks)
A representative of the company is to visit each of the areas being considered. He wishes to plan a journey of minimum length starting and ending in Leeds and visiting each of the other cities in the table once.
Assuming that the network satisfies the triangle inequality, - find an initial upper bound for the length of his journey,
- improve this upper bound to find an upper bound of less than 575 miles.
- By deleting Leeds, find a lower bound for his journey.
Turn over