Question 1 - A-Level Maths

The network above shows the distances, in miles, between seven gift shops, \(A , B\), \(C , D , E , F\) and \(G\).

The area manager needs to visit each shop. She will start and finish at shop A and wishes to minimise the total distance travelled.

By inspection, complete the two copies of the table of least distances below.
\includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-1_666_1136_141_863}
A \(B\) C \(D\) \(E\) \(F\) \(G\)
A - 15 36 53 23
B - 17 38 49 80 49
C 15 17 - 21 62 32
D 36 38 21 - 11 42
E 49 11 - 31 61
\(F\) 53 80 62 42 31 - 30
\(G\) 23 49 32 61 30 -
(4)
\(A\) \(B\) \(C\) \(D\) \(E\) \(F\) \(G\)
\(A\) - 15 36 53 23
\(B\) - 17 38 49 80 49
\(C\) 15 17 - 21 62 32
\(D\) 36 38 21 - 11 42
\(E\) 49 11 - 31 61
\(F\) 53 80 62 42 31 - 30
\(G\) 23 49 32 61 30 -
Starting at A, and making your method clear, find an upper bound for the route length, using the nearest neighbour algorithm.
(3)
By deleting A, and all of its arcs, find a lower bound for the route length.
(4) (Total 11 marks)