D1 June 2010 Q2

EdexcelOld spec9 marksMinimum Spanning Trees

Figure 1: network with arcs AC 30, AB 31, CF 29, CE 24, CD 22, DE 18, BD 24, DH 34, BH 38, EF 28, EG 26, FG 21, GH 33 — Figure 1

Figure 1 represents the distances, in metres, between eight vertices, A, B, C, D, E, F, G and H, in a network.

(a) Use Kruskal’s algorithm to find a minimum spanning tree for the network.
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 spanning tree. (3)

(b) Complete Matrix 1 in your answer book, to represent the network. (2)

(c) Starting at A, use Prim’s algorithm to determine a minimum spanning tree. You must clearly state the order in which you considered the vertices and the order in which you included the arcs. (3)

(d) State the weight of the minimum spanning tree. (1)

Mark scheme (a)

Scheme	Marks
DE GF DC \(\left\{\begin{matrix}\text{not CE}\\ \text{BD}\end{matrix}\right\}\) EG (not EF not CF) AC (not AB) GH	M1 A1 A1
	(3)

Notes

1M1: Kruskal’s algorithm – first 4 arcs selected chosen correctly.

1A1: All seven non-rejected arcs chosen correctly.

2A1: All rejections correct and in correct order and at correct time.

Mark scheme (c)

Scheme	Marks
AC CD DE BD GE GF GH	M1 A1 A1
	(3)

Notes

1M1: Prim’s algorithm – first four arcs chosen correctly, in order, or first five nodes chosen correctly, in order.{A,C,D,E,B….}

1A1: First six arcs chosen correctly or all 8 nodes chosen correctly, in order. {A,C,D,E,B,G,F,H}

2A1: All correct and arcs chosen in correct order.

Starting at	Minimum arcs required for M1	Nodes	order
A	AC CD DE DB	ACDEB(GFH)	15234(768)
B	BD DE DC	BDEC(GFAH)	(7)1423(658)
C	CD DE DB	CDEB(GFAH)	(7)4123(658)
D	DE DC DB	DECB(GFAH)	(7)4312(658)
E	ED DC DB	EDCB(GFAH)	(7)4321(658)
F	FG GE ED DC DB	FGEDCB(AH)	(7)654312(8)
G	GF GE ED DC DB	GFEDCB(AH)	(7)654321(8)
H	HG GF GE	HGFE(DCBA)	(8765)4321

Scheme	Marks
Weight: 174	B1
	(1)
	(9 marks)