D1 June 2018 Q1

EdexcelOld spec8 marksMinimum Spanning Trees

Figure 1: weighted network with vertices A to J — Figure 1

(a) Define the terms

(i) tree,

(ii) minimum spanning tree. (3)

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

(c) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree. (2)

Mark scheme (a)

Scheme	Marks
(i) A tree is a connected graph with no cycles	B1
(ii) A minimum spanning tree is a tree that contains all vertices and	B1
the total length of its arcs is as small as possible	B1
	(3)

Notes

In (a) all technical language used must be correct

ai1B1: Connected + no cycle(s) (must contain these two points – do not allow ‘circle’, ‘loop’ etc. for cycle(s)) – for connected allow ‘a graph in which a path exists between each pair of vertices’

aii2B1: Contains all (oe) and either vertices or nodes

aii3B1: Total length (of arcs) is minimised (must contain the two points regarding total and minimised/smallest but need not necessarily mention arcs e.g. ‘smallest total weight’ is sufficient for this mark). However ‘a MST is a tree that contains all the nodes and has the least possible weight’ would score B1B0 in (a)(ii) as they have ‘all the nodes’, but no explicit mention of ‘total’ (or equivalent e.g. ‘sum of’)

Mark scheme (b)

Scheme	Marks
AG, AF, GJ; FB, BC, BD; CH, DE	M1; A1; A1
	(3)

Notes

b1M1: First three arcs (AG, AF, GJ) correctly chosen, or first four nodes (A, G, F, J) correctly chosen in order. If any explicit rejections seen then M1 (max) only. A list of weights only scores M0. Candidates may apply Prim’s in matrix form so the order of the nodes may be seen at the top of a matrix – accept {1,-,-,-,-,3,2,-,4} for the M mark. Allow GJ for JG etc. throughout (b)

b1A1: First six arcs correctly chosen in order (AG, AF, GJ, FB, BC, BD), or all nodes correctly chosen in order (A, G, F, J, B, C, D, H, E). Candidates may apply Prim’s in matrix form so the order of the nodes may be seen at the top of a matrix – accept {1,5,6,7,9,3,2,8,4} – do not condone any missing numbers e.g. the number 9 must be above E

b2A1: CSO (correct solution only) – 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)

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

Scheme	Marks
	B1
(Weight of the tree is) 182	B1
	(2)
	(8 marks)