D1 June 2017 Q2

EdexcelOld spec7 marksMinimum Spanning Trees

Figure 3: weighted network of nine computer terminals A to J — Figure 3

Figure 3 represents nine computer terminals, A, B, C, D, E, F, G, H and J, at Pearsonby School. The school wishes to connect them to form a single computer network. The number on each arc represents the cost, in pounds, of connecting the corresponding computer terminals.

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

(b) State the minimum cost of connecting the nine computer terminals. (1)

It is discovered that some computer terminals are already connected. There are already direct connections along BD and FJ, as shown in bold in Diagram 1 in the answer book. It is decided to use these connections.

(c) Use Kruskal’s algorithm to find the minimum spanning tree that includes arcs BD and FJ. You must list the arcs in the order that you consider them. In each case, state whether or not you are adding the arcs to your spanning tree. (3)

Mark scheme (a)

Scheme	Marks
BC, BE, EH, CD; EF, FG; HJ, AG	M1; A1; A1
	(3)

Notes

a1M1: First four arcs correctly chosen in order (BC, BE, EH, CD) or first five nodes correctly chosen in order (B, C, E, H, D). If any explicit rejections seen at any point then M1 (max) only. Allow a list of weights for M1 only (10, 30, 25, 45). 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, 2, 5, 3, -, -, 4, -} for the M mark. Allow CB for BC etc. throughout (a) and (c)

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

a2A1: 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 B scores M1 only in (a) – must have the first four arcs (or five nodes) correct (and in the correct order). The most common misread is those that start at A so for M1 only – accept AG, GF, EF, EH or A, G, F, E, H or 75, 70, 52, 25

Scheme	Marks
(£) 380	B1
	(1)

Mark scheme (c)

Scheme	Marks
BC, EH, BE, reject CD, EF, reject BF, FG, reject HJ, AG (reject BG), (reject DA), (reject BA) (Note BD and FJ are already in the tree)	M1 A1 A1
	(3)
	(7 marks)

Notes

c1M1: Kruskal’s - first three arcs BC, EH, BE,…(or weights 10, 25, 30,…) chosen correctly in order and at least one rejection seen at some point. Ignore any reference to BD and FJ

c1A1: All six arcs BC, EH, BE, EF, FG, AG chosen correctly in order and no additional arcs. Ignore any reference to BD and FJ. Do not accept only a list of weights for this mark

c2A1: CAO all selections and rejections correct in the correct order and at the correct time. Ignore any reference to BD and FJ. Do not accept only a list of weights for this mark – do not need to see explicit rejection of BG, DA and/or BA for this mark

Listing all the arcs in order and then listing those arcs in the tree in the correct order is fine for full marks as this implies that rejections are correct and at the correct time
Listing all the arcs in order and just drawing the MST is M0

No misread if candidates use any other arcs instead of BD and/or FJ