D1 June 2013 (R) Q2

EdexcelOld spec8 marksMinimum Spanning Trees

	A	B	C	D	E	F
A	–	85	110	160	225	195
B	85	–	100	135	180	150
C	110	100	–	215	200	165
D	160	135	215	–	235	215
E	225	180	200	235	–	140
F	195	150	165	215	140	–

The table shows the average journey time, in minutes, between six towns, A, B, C, D, E and F.

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

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

Kruskal’s algorithm may also be used to find a minimum spanning tree.

(d) State three differences between Prim’s algorithm and Kruskal’s algorithm. (3)

Mark scheme (a)

Scheme	Marks
AB(85), BC(100), BD(135); BF(150), EF(140).	M1 A1; A1
	(3)

Notes

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

a1A1 First four arcs correctly chosen or all six nodes correctly chosen {A, B, C, D, F, E}. Order of nodes may be seen across the top of the matrix {1, 2, 3, 4, 6, 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	AB BC BD	ABCD(FE)	1234(65)
B	AB BC BD	BACD(FE)	2134(65)
C	BC AB BD	CBAD(FE)	3214(65)
D	BD AB BC	DBAC(FE)	3241(65)
E	EF BF AB	EFBA(CD)	43(56)12
F	EF BF AB	FEBA(CD)	43(56)21

Scheme	Marks
	B1
	(1)

Scheme	Marks
610 (minutes)	B1
	(1)

Mark scheme (d)

Scheme	Marks
E.g. (any three) Kruskal starts with the shortest arc, Prim starts with any node. It is necessary to check for cycles when using Kruskal, not with Prim. When using Prim the ‘growing’ tree is always connected. When using Kruskal arcs are considered in ascending order of weight. Prim can be used when the network is given in matrix form. Prim adds nodes to the growing tree, Kruskal adds arcs. Other correct statements also get credit	B1 B1 B1
	(3)
	(8 marks)

Notes

d1B1 One correct statement.

d2B1 A second correct statement.

d3B1 A third correct statement.

In part (d) all technical language must be correct (so do not condone point for vertex/node etc.)