A2 October 2021 Q3

EdexcelCurrent spec8 marksMinimum Spanning Trees Travelling Salesman

	A	B	C	D	E	F	G	H
A	–	24	42	48	34	37	32	22
B	24	–	40	35	30	41	39	44
C	42	40	–	21	26	45	38	36
D	48	35	21	–	32	37	29	27
E	34	30	26	32	–	34	40	28
F	37	41	45	37	34	–	43	41
G	32	39	38	29	40	43	–	38
H	22	44	36	27	28	41	38	–

Table 1

Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H.

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

(b) State the weight of the minimum spanning tree. (1)

	A	B	C	D	E	F	G	H
J	31	27	50	29	43	25	49	35

Table 2

Table 2 shows the distances, in miles, between town J and towns A, B, C, D, E, F, G and H.

Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels.

(c) Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav’s route. You must state your route and its length. (2)

(d) Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav’s route. (2)

Mark scheme (a)

Scheme	Marks	AO
Prim’s starting at A: AH, AB, DH; CD, CE; DG, EF	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

(a) M1: First three arcs correctly chosen in order {AH, AB, DH, …} or first four nodes correctly chosen in order {A, H, B, D,…}. If any rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of the matrix {1, 3, -, 4, -, -, -, 2} so please check the top of the matrix carefully

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

A1: cso – all arcs correct 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 183 (miles)	B1	2.2a
	(1)

Mark scheme (c)

Scheme	Marks	AO
NNA: J – F – E – C – D – H – A – B – G – J	B1	1.1b
Upper bound is 267 (miles)	B1	2.2a
	(2)

Notes

(c) B1: cao (for route – must return to J)

B1: cao (for upper bound of 267)

Scheme	Marks	AO
183 + 27 + 25 =…	M1	3.1b
… = 235 (miles)	A1	2.2a
	(2)
	(8 marks)