8 Salvadore is visiting six famous places in Barcelona: La Pedrera \(( L )\), Nou Camp \(( N )\), Olympic Village \(( O )\), Park Guell \(( P )\), Ramblas \(( R )\) and Sagrada Familia \(( S )\). Owing to the traffic system the time taken to travel between two places may vary according to the direction of travel.
The table shows the times, in minutes, that it will take to travel between the six places.
| \backslashbox{From}{To} | La Pedrera ( \(L\) ) | Nou Camp (N) | Olympic Village ( \(O\) ) | Park Guell (P) | Ramblas (R) | Sagrada Familia ( \(S\) ) |
| La Pedrera \(( L )\) | - | 35 | 30 | 30 | 37 | 35 |
| Nou Camp \(( N )\) | 25 | - | 20 | 21 | 25 | 40 |
| Olympic Village ( \(O\) ) | 15 | 40 | - | 25 | 30 | 29 |
| Park Guell ( \(P\) ) | 30 | 35 | 25 | - | 35 | 20 |
| Ramblas ( \(R\) ) | 20 | 30 | 17 | 25 | - | 25 |
| Sagrada Familia ( \(S\) ) | 25 | 35 | 29 | 20 | 30 | - |
- Find the total travelling time for:
- the route \(L N O L\);
- the route \(L O N L\).
- Give an example of a Hamiltonian cycle in the context of the above situation.
- Salvadore intends to travel from one place to another until he has visited all of the places before returning to his starting place.
- Show that, using the nearest neighbour algorithm starting from Sagrada Familia \(( S )\), the total travelling time for Salvadore is 145 minutes.
- Explain why your answer to part (c)(i) is an upper bound for the minimum travelling time for Salvadore.
- Salvadore starts from Sagrada Familia ( \(S\) ) and then visits Ramblas ( \(R\) ). Given that he visits Nou Camp \(( N )\) before Park Guell \(( P )\), find an improved upper bound for the total travelling time for Salvadore.