A2 October 2020 Q1

EdexcelCurrent spec6 marksMinimum Spanning Trees

1. The table below shows the lengths, in km, of the roads in a network connecting seven towns, A, B, C, D, E, F and G.

	A	B	C	D	E	F	G
A	–	24	–	22	35	–	–
B	24	–	25	27	–	–	–
C	–	25	–	33	31	36	26
D	22	27	33	–	–	42	–
E	35	–	31	–	–	37	29
F	–	–	36	42	37	–	40
G	–	–	26	–	29	40	–

(a) By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book. (2)

Diagram 1: the network drawn without the arcs from D: AB 24, AE 35, BC 25, CE 31, CF 36, CG 26, EF 37, EG 29, FG 40; vertex D has no arcs — Diagram 1

(b) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)

Scheme	Marks	AO
	M1 A1	1.1b 1.1b
	(2)

Mark scheme (b)

Scheme	Marks	AO
Kruskal’s algorithm: AD, AB, BC, CG, reject BD, EG, reject CE, reject CD, reject AE, CF (reject EF, reject FG, reject DF)	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

(b) M1: Kruskal’s algorithm – first three arcs correctly chosen and at least one rejection seen at some point

A1: All six arcs selected correctly AD, AB, BC, CG, EG, CF only

A1: CSO – all selections and rejections correct (in correct order and at the correct time)

Scheme	Marks	AO
Weight of MST: 162 (km)	B1	1.1b
	(1)
	(6 marks)