4 David, a tourist, wishes to visit five places in Rome: Basilica ( \(B\) ), Coliseum ( \(C\) ), Pantheon ( \(P\) ), Trevi Fountain ( \(T\) ) and Vatican ( \(V\) ). He is to start his tour at one of the places, visit each of the other places, before returning to his starting place.
The table shows the times, in minutes, to travel between these places. David wishes to keep his travelling time to a minimum.
| \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { P }\) | \(T\) | \(V\) |
| \(\boldsymbol { B }\) | - | 43 | 57 | 52 | 18 |
| \(\boldsymbol { C }\) | 43 | - | 18 | 13 | 56 |
| \(P\) | 57 | 18 | - | 8 | 48 |
| \(T\) | 52 | 13 | 8 | - | 51 |
| \(V\) | 18 | 56 | 48 | 51 | - |
- Find the total travelling time for the tour TPVBCT.
- Find the total travelling time for David's tour using the nearest neighbour algorithm starting from \(T\).
- Explain why your answer to part (a)(ii) is an upper bound for David's minimum total travelling time.
- By deleting \(B\), find a lower bound for the total travelling time for the minimum tour.
- Explain why your answer to part (b)(i) is a lower bound for David's minimum total travelling time.
- Sketch a network showing the edges that give the lower bound found in part (b)(i) and comment on its significance.