A2 June 2024 Q2

EdexcelCurrent spec13 marksMinimum Spanning Trees Travelling Salesman

2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

	A	B	C	D	E	F	G	H	J
A	–	50	59	26	50	40	87	63	59
B	50	–	28	61	79	63	45	64	48
C	59	28	–	33	57	35	70	36	45
D	26	61	33	–	24	64	71	37	33
E	50	79	57	24	–	40	64	30	31
F	40	63	35	64	40	–	47	70	71
G	87	45	70	71	64	47	–	34	67
H	63	64	36	37	30	70	34	–	33
J	59	48	45	33	31	71	67	33	–

(a) Use Prim’s algorithm, starting at D, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree. (3)

(b) State the weight of the minimum spanning tree found in part (a). (1)

Diagram 1: the nine vertices A, B, C, D, E, F, G, H and J with no arcs — Diagram 1

A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.

(d) Use your answer to part (b) to calculate an initial upper bound for the length of the historian’s route. (1)

(e)

(i) Use the nearest neighbour algorithm, starting at D, to find an upper bound for the length of the historian’s route.

(ii) Write down the route which gives this upper bound. (3)

Using the nearest neighbour algorithm, starting at F, an upper bound of length 352 miles was found.

(f) State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer. (1)

(g) By deleting A and all of its arcs, find a lower bound for the length of the historian’s route. (2)

By deleting J and all of its arcs, a lower bound of length 274 miles was found.

(h) State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer. (1)

Mark scheme (a)

Scheme	Marks	AO
Prim’s starting at D: DE, AD, EH; EJ, CD, BC; GH, CF	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: First three arcs correctly chosen in order {DE, AD, EH, …} or first four nodes correctly chosen in order{D, E, A, H,…}. If any rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of the matrix {3, -, -, 1, 2, -, -, 4, -} so please check the top of the matrix carefully. If they start at any other vertex M1 only for the first three arcs in order (Starting at A AD DE EH).

A1: First six arcs correctly chosen in order {DE, AD, EH, EJ, CD, BC, …} or all nine nodes correctly chosen in order{D, E, A, H, J, C, B, G, F}. Order of nodes may be seen at the top of the matrix so for the first two marks accept {3, 7, 6, 1, 2, 9, 8, 4, 5} (do not condone any missing numbers e.g. the number 9 must be above F)

A1: CSO – all arcs correctly stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

Scheme	Marks	AO
Weight of MST is 241 (miles)	B1	1.1b
	(1)

Scheme	Marks	AO
	B1	1.1b
	(1)

Scheme	Marks	AO
482 (miles)	B1ft	1.1b
	(1)

Mark scheme (e)

Scheme	Marks	AO
NNA starting at D: D – E – H – J – C – B – G – F – A – D 24 + 30 + 33 + 45 + 28 + 45 + 47 + 40 + 26 = 318 (miles)	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: Nearest neighbour route starting at D – must have at least D – E – H – J – C – B – … allow if stated in terms of arcs (DE EH HJ JC CB) but not for just numbering across the matrix

A1: CAO route (must return to D and can be stated as arcs DE EH HJ JC CB BG GF FA AD)

A1: CAO length (318)

Mark scheme (f)

Scheme	Marks	AO
The best upper bound is the one found in (e) as 318 is less than both 352 and 482	dB1ft	2.2a
	(1)

Notes

dB1ft: Follow through their value from (e) (must include reason e.g. 318 is the lowest of the values found, but they do not need to mention the other values) Must score at least M1 in (e)

Mark scheme (g)

Scheme	Marks	AO
(241 – 26) + 26 + 40 = 281 (miles)	M1 A1	3.1b 2.2a
	(2)

Notes

M1: (weight of their MST from (b) or 241 only) – 26 + 26(AD) + 40(AF) (oe so may not see the – 26 + 26). A correct answer of 281 can imply this (and the next) mark. Alternatively may delete A and find RMST (215) and add AD (26) and AF (40)

A1: 281

Mark scheme (h)

Scheme	Marks	AO
The best lower bound is the one found in (g) as 281 is greater than 274	dB1ft	2.2a
	(1)
	(13 marks)

Notes

dB1ft: Follow through their “281” with 274 and makes conclusion (e.g. 281 is the bigger value, but they do not need to mention 274). Must be a smaller value than their answer to (f) and must score at least M1 in (g)