D2 June 2015 Q3

EdexcelOld spec12 marksTravelling Salesman

	A	B	C	D	E	F	G
A	–	\(x\)	41	43	38	21	30
B	\(x\)	–	27	38	19	29	51
C	41	27	–	24	37	35	40
D	43	38	24	–	44	52	25
E	38	19	37	44	–	20	28
F	21	29	35	52	20	–	49
G	30	51	40	25	28	49	–

The network represented by the table shows the least distances, in km, between seven theatres, A, B, C, D, E, F and G.

Jasmine needs to visit each theatre at least once starting and finishing at A. She wishes to minimise the total distance she travels. The least distance between A and B, is \(x\) km, where \(21 \lt x \lt 27\)

(a) Using Prim’s algorithm, starting at A, obtain a minimum spanning tree for the network.
You should list the arcs in the order in which you consider them. (2)

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

The nearest neighbour algorithm starting at F gives a route of F – E – B – A – G – D – C – F.

(d) State which of these two nearest neighbour routes gives the better upper bound. Give a reason for your answer. (2)

Starting by deleting A, and all of its arcs, a lower bound of 159 km for the length of the route is found.

(e) Find \(x\), making your method clear. (3)

(f) Write down the smallest interval that you can be confident contains the optimal length of Jasmine’s route. Give your answer as an inequality. (2)

Mark scheme (a)

Scheme	Marks
Prim: AF, EF, BE, BC, CD, DG	M1 A1
	(2)

Notes

a1M1: Must be using Prim’s algorithm not NNA – if any arc creates a cycle then M0. First four arcs (or all 7 nodes / or numbers across the top of the matrix) selected correctly. Award M1 only for a correct tree with no working. Award M1 only for the first four arcs (oe) selected correctly if starting at a different node than A

a1A1: CAO (order of arc selection clear)

Scheme	Marks
2 × 136 = 272 (km)	B1
	(1)

Mark scheme (c)

Scheme	Marks
A F E B C D G A	B1
21 20 19 27 24 25 30 = 166 (km)	B1
	(2)

Notes

c1B1: CAO – must be either in terms of nodes or arcs (not weights)

c2B1: CAO (166)

Mark scheme (d)

Scheme	Marks
Starting at F route length is \(153 + x\)	B1
With \(x \gt 21\), \(153 + x\) is greater than 166 so the better upper bound is the one starting at A	DB1
	(2)

Notes

d1B1: Either \(153 + x\) or states a value in the interval 174 < value < 180 or considers one of the intervals 174 < value < 180 or 175 \(\leqslant\) value \(\leqslant\) 179

d2DB1: Correct argument that A gives the better upper bound. Must be considering either \(x \gt 21\) or \(x \geqslant 22\) with 153 (so expect to see as a minimum the mention of > 174 or \(\geqslant\) 175) – must be clear that the upper bound starting at A is the better upper bound. This mark is dependent on the previous B mark in (d)

Mark scheme (e)

Scheme	Marks
Length of RMST = 115	B1
\(115 + 21 + x = 159 \therefore x = 23\) (km)	M1 A1
	(3)

Notes

e1B1: CAO (length of RMST) – the length (115 or 19 + 20 + 27 + 24 + 25) must be either explicitly stated or seen in their working (not just implied by their working)

e1M1: Adding the correct two least values (21 and \(x\)) to their RMST length (their RMST may be incorrect but must contain only 5 arcs) and equating to 159. Accept, for example, \(136 + x = 159\) or \(136 + 23 = 159\) or \(115 + 21 + 23 = 159\) or equivalent calculations using the length of their RMST

e1A1: CAO (must be clear that (\(x\) =) 23 not just embedded in a calculation)

Mark scheme (f)

Scheme	Marks
159 \(\leqslant\) optimal \(\leqslant\) 166 [accept 159 < optimal \(\leqslant\) 166]	B2,1,0
	(2)
	12 marks

Notes

f1B1: Any indication of an interval containing 159 (as a lower bound) and their stated better upper bound from (d)

f2B1: CAO either 159 \(\leqslant\) optimal (oe) \(\leqslant\) 166 or 159 < optimal (oe) \(\leqslant\) 166