5 Angelo is visiting six famous places in Palermo: \(A , B , C , D , E\) and \(F\). He intends to travel from one place to the next until he has visited all of the places before returning to his starting place. Due to the traffic system, the time taken to travel between two places may be different dependent on the direction travelled.
The table shows the times, in minutes, taken to travel between the six places.
| \backslashbox{From}{To} | A | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | E | \(F\) |
| A | - | 25 | 20 | 20 | 27 | 25 |
| \(\boldsymbol { B }\) | 15 | - | 10 | 11 | 15 | 30 |
| \(\boldsymbol { C }\) | 5 | 30 | - | 15 | 20 | 19 |
| \(\boldsymbol { D }\) | 20 | 25 | 15 | - | 25 | 10 |
| \(\boldsymbol { E }\) | 10 | 20 | 7 | 15 | - | 15 |
| F | 25 | 35 | 29 | 20 | 30 | - |
- Give an example of a Hamiltonian cycle in this context.
- Show that, if the nearest neighbour algorithm starting from \(F\) is used, the total travelling time for Angelo would be 95 minutes.
- Explain why your answer to part (b)(i) is an upper bound for the minimum travelling time for Angelo.
- Angelo starts from \(F\) and visits \(E\) next. He also visits \(B\) before he visits \(D\). Find an improved upper bound for Angelo's total travelling time.
\includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-11_2484_1709_223_153}