Problem

The table below shows the distances, in km, between six data collection points, A, B, C, D, E and F.

	A	B	C	D	E	F
A	–	35	42	55	48	50
B	35	–	40	49	52	31
C	42	40	–	47	53	49
D	55	49	47	–	39	44
E	48	52	53	39	–	52
F	50	31	49	44	52	–

Ferhana must visit each data collection point. She will start and finish at A and wishes to minimise the total distance she travels.

(a) Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the distance Ferhana must travel. Make your method clear.

(b) Starting by deleting B, and all of its arcs, find a lower bound for the distance Ferhana must travel. Make your calculation clear.

(Total 5 marks)