7 Rob delivers bread to six shops \(A , B , C , D , E\) and \(F\). Each day, Rob starts at shop \(A\), travels to each of the other shops before returning to shop \(A\). The table shows the distances, in miles, between the shops.
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) | \(\boldsymbol { F }\) |
| \(\boldsymbol { A }\) | - | 8 | 6 | 9 | 12 | 7 |
| \(\boldsymbol { B }\) | 8 | - | 10 | 14 | 13 | 8 |
| \(\boldsymbol { C }\) | 6 | 10 | - | 7 | 16 | 10 |
| \(\boldsymbol { D }\) | 9 | 14 | 7 | - | 15 | 5 |
| \(\boldsymbol { E }\) | 12 | 13 | 16 | 15 | - | 11 |
| \(\boldsymbol { F }\) | 7 | 8 | 10 | 5 | 11 | - |
- Find the length of the tour \(A B C D E F A\).
- Find the length of the tour obtained by using the nearest neighbour algorithm starting from \(A\).
- By deleting \(A\), find a lower bound for the length of a minimum tour.
- By deleting \(F\), another lower bound of 45 miles is obtained for the length of a minimum tour.
The length of a minimum tour is \(T\) miles. Write down the smallest interval for \(T\) which can be obtained from your answers to parts (a) and (b), and the information given in this part.
(3 marks)