D1 June 2014 Q1

EdexcelOld spec5 marksMinimum Spanning Trees

	Art	Biology	Chemistry	Drama	English	French	Graphics
Art (A)	–	61	93	73	50	48	42
Biology (B)	61	–	114	82	83	63	58
Chemistry (C)	93	114	–	59	94	77	88
Drama (D)	73	82	59	–	89	104	41
English (E)	50	83	94	89	–	91	75
French (F)	48	63	77	104	91	–	68
Graphics (G)	42	58	88	41	75	68	–

The table shows the travelling times, in seconds, to walk between seven departments in a college.

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

(b) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. (1)

Mark scheme (a)

Scheme	Marks
AG, DG, AF; AE BG; CD	M1 A1 A1
	(3)

Notes

a1M1 First three arcs correctly chosen in order (AG, DG, AF, … or weights 42, 41, 48, …) or first four nodes correctly chosen in order. {A.G,D,F,…} 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.

a1A1 First five arcs correctly chosen in order (AG, DG, AF, AE, BG or weights 42, 41, 48, 50, 58,…) or all seven nodes correctly chosen in order. {A,G,D,F,E,B,C}. Order of nodes may be seen at the top of the matrix so for the first two marks accept {1, 6, 7, 3, 5, 4, 2} (do not condone any missing numbers e.g. the number 7 must be above C).

a2A1 CSO - all arcs correct and chosen in the correct order. They must be considering arcs for this final mark (do not accept a list of the weights of each arc, nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen).

Misread: Starting at a node other than A scores M1 only – must have the first three arcs (or four nodes or numbers) correct (and in the correct order).

Starting at	Minimum arcs required for M1	Nodes	Order
A	AG DG AF	AGDF(EBC)	1(6)(7)3(5)42
B	BG DG AG	BGDA(FEC)	41(7)3(6)(5)2
C	CD DG AG	CDGA(FEB)	4(7)12(6)(5)3
D	DG AG AF	DGAF(EBC)	3(6)(7)1(5)42
E	EA AG DG	EAGD(FBC)	2(6)(7)41(5)3
F	FA AG DG	FAGD(EBC)	2(6)(7)4(5)13
G	GD AG AF	GDAF(EBC)	3(6)(7)2(5)41

Scheme	Marks
Weight of tree = 298 (s)	B1
	(1)
	(5 marks)