D1 January 2010 Q2

EdexcelOld spec9 marksGraphs & Networks Minimum Spanning Trees

2. Prim’s algorithm finds a minimum spanning tree for a connected graph.

(a) Explain the terms

(i) connected graph,

(ii) tree,

(iii) spanning tree.

(3)

(b) Name an alternative algorithm for finding a minimum spanning tree. (1)

	Cambridge	London	Norwich	Oxford	Portsmouth	Salisbury	York
Cambridge (C)	-	60	62	81	132	139	156
London (L)	60	-	116	56	74	88	211
Norwich (N)	62	116	-	144	204	201	181
Oxford (O)	81	56	144	-	84	63	184
Portsmouth (P)	132	74	204	84	-	43	269
Salisbury (S)	139	88	201	63	43	-	248
York (Y)	156	211	181	184	269	248	-

Figure 2

Figure 2 shows the distances by road, in miles, between seven cities.

(c)

(i) Use Prim’s algorithm, starting at London, to find the minimum spanning tree for these cities. You must clearly state the order in which you selected the edges of your tree, and the weight of the final tree.

(ii) Draw your tree using the vertices given in Diagram 2 in the answer book.

(5)

Mark scheme (a)

Scheme	Marks
(i) All pairs of vertices connected by a path, but not describing complete graph.	B1
(ii) No cycles	B1
(iii) All nodes connected (accept definition of minimum spanning tree)	B1
	(3)

Tree: Y–C, C–N, C–L, L–O, O–S, S–P — Mark scheme (c)

Scheme	Marks
(i) L-O 56 L-C 60	M1
C-N 62 O-S 63	A1
S-P 43 C-Y 156	A1
Total length 440 (miles)	A1 =B1
(ii) Tree correct	B1
	(5)
	(9 marks)

Started at	Minimum arcs	nodes	Numbers
C	CL,LO,CN,…..	CLONSPY	1243657
N	NC,CL,LO,OS,SP,CY	NCLOSPY	2314657
O	OL,LC,CN,OS,….	OLCNSPY	3241657
P	PS,SO,OL,LC,CN.CY	PSOLCNY	5463127
S	SP.SO,…	SPOLCNY	5463217
Y	YC,CL,LO,CN,..	YCLONSP	2354761

Scheme	Marks
Kruskal’s (algorithm)	B1
	(1)

Notes