D1 June 2012 Q3
3.
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | - | 15 | 19 | - | 22 | 24 | - |
| B | 15 | - | - | 8 | 13 | - | - |
| C | 19 | - | - | 12 | - | 16 | - |
| D | - | 8 | 12 | - | 10 | - | 18 |
| E | 22 | 13 | - | 10 | - | 15 | 16 |
| F | 24 | - | 16 | - | 15 | - | 17 |
| G | - | - | - | 18 | 16 | 17 | - |
The table shows the lengths, in km, of a network of roads between seven villages, A, B, C, D, E, F and G.
(a) Complete the drawing of the network in Diagram 1 of the answer book by adding the necessary arcs from vertex D together with their weights. (2)
(b) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)
(c) Draw the minimum spanning tree using the vertices provided in Diagram 2 in the answer book. (1)
(d) State the weight of the minimum spanning tree. (1)
| Scheme | Marks |
|---|---|
 | 1B1 2B1 |
| (2) |
Notes
a1B1 All four arcs CAO (+ see below)
a2B1 All four weights CAO.
Additional notes for (a)
- If B0 B0 but three arcs and their weights correct then give B1 B0.
- If extra arcs and weights remove second B mark (so B1 B0 max)
- If just one of DB or DE or DC missing, mark remainder of question as a misread.
- If two or more arcs are missing send to review.
- If DF used instead of DG, ignore references to this in (b)
| Scheme | Marks |
|---|---|
| BD(8), DE(10), CD(12), reject BE(13), {EF(15), AB(15)}, {EG(16), reject CF(16)} reject remainder of arcs. | M1 1A1 2A1 |
| (3) |
Notes
b1M1 First three arcs correctly chosen and at least one rejection seen at some point. (Kruskal not Prim.)
b1A1 First five arcs selected correctly; BD, DE, CD, then (in either order) EF, AB
b2A1 CAO including necessary rejections.
| Scheme | Marks |
|---|---|
 | B1 |
| (1) |
Notes
c1B1 CAO condone missing weights.
| Scheme | Marks |
|---|---|
| Weight of tree = 76 (km) | B1 |
| (1) | |
| (7 marks) |
Notes
d1B1 CAO