Problem Statement
A medical supply courier must visit 5 clinics $A, B, C, D, E$ connected by roads with distance table:\n\n$A-B=12, A-C=15, A-D=20, A-E=18$\n$B-C=10, B-D=16, B-E=14$\n$C-D=11, C-E=13$\n$D-E=9$
**(a)** [4 marks] Use the Nearest Neighbor algorithm starting at clinic $A$ to find an upper bound for the optimal Hamiltonian cycle.
**(b)** [4 marks] By deleting vertex $A$ and constructing a minimum spanning tree on the remaining vertices, find a lower bound for the optimal tour.
Verified Solution & Marking Scheme
Part (a) [M1]
From $A$, nearest is $B (12)$. From $B$, nearest unvisited is $C (10)$. From $C$, nearest unvisited is $D (11)$. From $D$, nearest unvisited is $E (9)$.
Part (a) [A1]
Return edge: from $E$ back to $A$ is $18$.
Part (a) [A1]
Tour: $A \to B \to C \to D \to E \to A$
Part (a) [A1]
Upper bound length $= 12 + 10 + 11 + 9 + 18 = 60\text{ km}$