4 Sarah is a mobile hairdresser based at \(A\). Her day's appointments are at five places: \(B , C , D , E\) and \(F\). She can arrange the appointments in any order. She intends to travel from one place to the next until she has visited all of the places, starting and finishing at \(A\). The following table shows the times, in minutes, that it takes to travel between the six places.
| \cline { 2 - 7 }
\multicolumn{1}{c|}{} | \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) | \(\boldsymbol { F }\) |
| \(\boldsymbol { A }\) | - | 15 | 11 | 14 | 27 | 12 |
| \(\boldsymbol { B }\) | 15 | - | 13 | 19 | 24 | 15 |
| \(\boldsymbol { C }\) | 11 | 13 | - | 10 | 19 | 12 |
| \(\boldsymbol { D }\) | 14 | 19 | 10 | - | 26 | 15 |
| \(\boldsymbol { E }\) | 27 | 24 | 19 | 26 | - | 27 |
| \(\boldsymbol { F }\) | 12 | 15 | 12 | 15 | 27 | - |
- Sarah decides to visit the places in the order \(A B C D E F A\). Find the travelling time of this tour.
- Explain why this answer can be considered as being an upper bound for the minimum travelling time of Sarah's tour.
- Use the nearest neighbour algorithm, starting from \(A\), to find another upper bound for the minimum travelling time of Sarah's tour.
- By deleting \(A\), find a lower bound for the minimum travelling time of Sarah's tour.
- Sarah thinks that she can reduce her travelling time to 75 minutes. Explain why she is wrong.