D1 January 2011 Q3
3.
(a) Use Kruskal’s algorithm to find a minimum spanning tree for the network shown in Figure 2. 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 a minimum spanning tree for the network in Figure 2. You must clearly state the order in which you include the arcs in your tree. (3)
(c) Draw a minimum spanning tree for the network in Figure 2 using the vertices given in Diagram 1 of the answer book. State the weight of the minimum spanning tree. (2)
A new spanning tree is required which includes the arcs DI and HG, and which has the lowest possible total weight.
(d) Explain which algorithm you would choose to complete the tree, and how the algorithm should be adapted. (You do not need to find the tree.) (2)
| Scheme | Marks |
|---|---|
| CI CD (not DI) EF FI (not EI not DE) \(\left\{\begin{matrix}\text{BC}\\ \text{HI}\end{matrix}\right\}\) (not BI) GF | M1 A1 |
| (not GI not HG) AB | A1 |
| (3) |
Notes
1M1: Kruskal’s algorithm – first 4 arcs selected chosen correctly.
1A1: All eight non-rejected arcs chosen correctly.(Working seen in (a))
2A1: All rejections correct and in correct order and at correct time.
| Scheme | Marks |
|---|---|
| AB BC CI CD FI EF IH FG | 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, B,C,I, D} (arcs not arc lengths)
1A1: First six arcs chosen correctly; all 9 nodes chosen correctly, in order.{A,B,C,I,D,F,E,H,G}[1 2 3 5 7 6 9 8 4]
2A1: cso
| Scheme | Marks |
|---|---|
 | B1 |
| Weight: 270 | B1 |
| (2) |
Notes
1B1: cao (condone lack of numbers)
2B1: 270 cao
| Scheme | Marks |
|---|---|
| Start off the tree with DI and HG and then apply Kruskal’s algorithm | B2,1, 0 |
| (2) | |
| (10 marks) |
Notes
1B1: Kruskal’s algorithm + some argument
2B1: Kruskal’s algorithm + start with the two arcs. (o.e)