7 Fred delivers bread to five shops, \(A , B , C , D\) and \(E\). Fred starts his deliveries at shop \(B\), and travels to each of the other shops once before returning to shop \(B\). Fred wishes to keep his travelling time to a minimum.
The table shows the travelling times, in minutes, between the shops.
| \cline { 2 - 6 }
\multicolumn{1}{c|}{} | \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) |
| \(\boldsymbol { A }\) | - | 3 | 11 | 15 | 5 |
| \(\boldsymbol { B }\) | 3 | - | 18 | 12 | 4 |
| \(\boldsymbol { C }\) | 11 | 18 | - | 5 | 16 |
| \(\boldsymbol { D }\) | 15 | 12 | 5 | - | 10 |
| \(\boldsymbol { E }\) | 5 | 4 | 16 | 10 | - |
- Find the travelling time for the tour \(B A C D E B\).
- Use the nearest neighbour algorithm, starting at \(B\), to find another upper bound for the travelling time for Fred's tour.
- By deleting \(C\), find a lower bound for the travelling time for Fred's tour.
- Sketch a network showing the edges that give you the lower bound in part (c) and comment on its significance.