D1 January 2012 Q1

EdexcelOld spec8 marksMinimum Spanning Trees

1.

Figure 1: network with arcs AB 25, AD 19, BC 21, BE 30, CD 11, CF 15, DF 16, DH 39, EF 33, EG 13, FG 37, FH 40, HG 57
Figure 1

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

(a) Use Kruskal’s algorithm to find the 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) Starting at A, use Prim’s algorithm to find the minimum spanning tree. You must clearly state the order in which you selected the arcs of your tree. (3)
(c) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. (1)
(d) State the weight of the tree. (1)
‹ Previous20 of 31 in Minimum Spanning TreesNext ›