D2 June 2017 Q1

EdexcelOld spec7 marksTravelling Salesman

	A	B	C	D	E	F
A	–	83	75	82	69	97
B	83	–	94	103	77	109
C	75	94	–	97	120	115
D	82	103	97	–	105	125
E	69	77	120	105	–	88
F	97	109	115	125	88	–

The table above shows the least distances, in km, between six towns, A, B, C, D, E and F.

(a) Starting at A, and making your working clear, find an initial upper bound for the travelling salesperson problem for this network, using

(i) the minimum spanning tree method,

(ii) the nearest neighbour algorithm.

(5)

By deleting A, and all of its arcs, a lower bound for the travelling salesperson problem for this network is found to be 500 km.

By deleting B, and all of its arcs, the corresponding lower bound is found to be 474 km.

(b) Using the results from (a) and the given lower bounds, write down the smallest interval that you can be confident contains the solution to the travelling salesperson problem for this network. (2)

Mark scheme (a)

Scheme	Marks
(i) Prim’s starting from A: AE, AC, BE, AD; EF	M1 A1
\(2 \times 391 = 782\)	B1
(ii) Nearest neighbour: A – E – B – C – D – F – A	M1
69 77 94 97 125 97 = 559	A1
	(5)

Notes

a1M1: First four arcs (or first five nodes: A, E, C, B, D or equivalent numbers across the top of the table {1, 4, 3, 5, 2, -}) selected correctly. Award M1 only for a correct tree with no working or for a correct tree starting at a different node

a1A1: CAO (order of arcs correct or all six nodes correct: A, E, C, B, D, F – but not just the numbers across the top of the table)

a1B1: CAO (782) – must follow from the correct MST (so dependent on at least the M mark in (a)(i)) – do not isw if attempt at short cuts reduces this value

a2M1: Nearest neighbour A – E – B – C – D – F – (condone lack of return to start) or correct route length of 559. Accept AE, EB, BC, CD, DF but do not accept weights only

a2A1: CAO both route (either in terms of vertices or arcs but not weights) and length correct

Mark scheme (b)

Scheme	Marks
\(500 \leqslant \text{length} \leqslant 559\) (accept \(500 \lt \text{length} \leqslant 559\))	B2, 1, 0
	(2)
	7 marks

Notes

b1B1: Any indication of an interval from 500 to their 559 (their 559 > 500 and is the smallest value from either the MST method or NN method – must have stated two values in (a) but ignore how these values were derived)

b2B1: \(500 \leqslant \text{length} \leqslant 559\) or \(500 \lt \text{length} \leqslant 559\) (no ft on this mark) – accept set notation e.g. [500,559] or (500, 559]