D1 June 2013 Q3

EdexcelOld spec10 marksMinimum Spanning Trees

	A	B	C	D	E	F
A	-	15	6	9	-	-
B	15	-	12	-	14	-
C	6	12	-	7	10	-
D	9	-	7	-	11	17
E	-	14	10	11	-	5
F	-	-	-	17	5	-

The table shows the times, in days, needed to repair the network of roads between six towns, A, B, C, D, E and F, following a flood.

(a) Use Prim’s algorithm, starting at A, to find the minimum connector for this network. You must list the arcs that form your tree in the order that you selected them. (3)

(b) Draw your minimum connector using the vertices given in Diagram 1 in the answer book. (1)

(c) Add arcs from D, E and F to Diagram 2 in the answer book, so that it shows the network of roads shown by the table. (2)

(d) Use Kruskal’s algorithm to find the minimum connector. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum connector. (3)

(e) State the minimum time needed, in days, to reconnect the six towns. (1)

Mark scheme (a)

Scheme	Marks
AC, CD, CE; EF; BC	M1; A1; A1
	(3)

Notes

Accept the weight of each arc to represent the arcs (as each value is unique).

a1M1 Prim’s – first three arcs correctly chosen or first four nodes correctly chosen {A, C, D, E, ...}. Any rejections seen during selection M0. Order of nodes may be seen at the top of the matrix {1, – , 2, 3, 4, –}

a1A1 First four arcs correctly chosen or all six nodes correctly chosen {A, C, D, E, F, B}. Order of nodes may be seen at the top of the matrix {1, 6, 2, 3, 4, 5}

a2A1 CSO (must be considering arcs for this final mark).

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

Starting at	Minimum arcs required for M1	Nodes	Order
A	AC CD CE	ACDE(FB)	1(6)234(5)
B	BC AC CD	BCAD(EF)	3124(56)
C	AC CD CE	CADE(FB)	2(6)134(5)
D	CD AC CE	DCAE(FB)	3(6)214(5)
E	EF CE AC	EFCA(DB)	4(6)3(5)12
F	EF CE AC	FECA(DB)	4(6)3(5)21

Scheme	Marks
	B1
	(1)

Network: AB 15, AC 6, AD 9, BC 12, BE 14, CD 7, CE 10, DE 11, DF 17, EF 5 — Mark scheme (c)

Scheme	Marks
	B1 B1
	(2)

Mark scheme (d)

Scheme	Marks
EF, AC, CD, reject AD, CE, reject DE, CB	M1 A1 A1
	(3)

Notes

d1M1 Kruskal’s – first three arcs correctly chosen and at least one rejection seen at some point.

d1A1 All five arcs selected correctly EF, AC, CD, CE, CB.

d2A1 CAO All selections and rejections correct (in correct order and at the correct time).

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

SC for part (d): If the network diagram is incorrect in part (c) and it is clear that the candidate has used part (c) (instead of the original table) to answer part (d) then award M1 only for the first three arcs correctly chosen and at least one rejection seen at some point provided their network is connected and contains at least nine arcs.

Scheme	Marks
Time = 40 (days)	B1
	(1)
	(10 marks)