D2 June 2013 Q1

EdexcelOld spec12 marksTravelling Salesman

	A	B	C	D	E
A	–	15	19	25	20
B	15	–	15	15	25
C	19	15	–	22	11
D	25	15	22	–	18
E	20	25	11	18	–

The table shows the least distances, in km, between five hiding places, A, B, C, D and E.

Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A, and wishes to minimise the total distance travelled.

(a) Use Prim’s algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear. (2)

(b) Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie’s route. (1)

(d) State the better upper bound from your answers to (b) and (c). (1)

(e) Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie’s route. (4)

(f) Consider your answers to (d) and (e) and hence state an optimal route. (1)

Minimum spanning tree: AB 15, BC 15, CE 11, BD 15 — Mark scheme (a)

Scheme	Marks
e.g. starting from A: AB, BD, BC, CE or AB, BC, CE, BD	M1 A1
	(2)

Scheme	Marks
2 x 56 = 112	B1
	(1)

Mark scheme (c)

Scheme	Marks
A B C E D A 15 15 11 18 25 = 84 and A B D E C A 15 15 18 11 19 = 78	M1 A1 A1
	(3)

Notes

c1M1 Nearest Neighbour either A-B-C-E-D- or A-B-D-E-C- (condone lack of return to start). Accept 12354 or 12534 across the top of the matrix.

c1A1 1 route and length CAO (Do not ISW if route length is doubled)

c2A1 both routes and lengths CAO (Do not ISW if route lengths are doubled)

Scheme	Marks
78 is the better upper bound	B1ft
	(1)

Residual minimum spanning tree AC 19, CE 11, ED 18, with dashed arcs from B: BA 15, BC 15, BD 15 — Mark scheme (e)

Scheme	Marks
	1M1 A1
Lower bound = 48 + 15 + 15 = 78	2M1 A1
	(4)

Mark scheme (f)

Scheme	Marks
The route is ABDECA (The optimal route length is 78, since upper bound = lower bound)	B1
	(1)
	(12 marks)

Notes

f1B1 CAO, accept any start point for the correct tour, but must return to start. Dependent on their answer to part (d) = their answer to part (e).