D1 June 2011 Q2

EdexcelOld spec8 marksGraphs & NetworksMinimum Spanning Trees

2.

Figure 1: network with arcs AC 14, AB 10, BC 13, CF 18, CE 17, BF 20, BE 15, BD 14, DF 19, EF 18, DE 12
Figure 1
(a) Define the terms
(i) tree,
(ii) minimum spanning tree.
(3)
(b) Use Kruskal’s algorithm to find a minimum spanning tree for the network shown in Figure 1. 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)
(c) Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book. (1)
(d) State whether your minimum spanning tree is unique. Justify your answer. (1)
‹ Previous9 of 16 in Graphs & NetworksNext ›