D1 January 2009 Q2
2.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | - | 24 | - | - | 23 | 22 |
| B | 24 | - | 18 | 19 | 17 | 20 |
| C | - | 18 | - | 11 | 14 | - |
| D | - | 19 | 11 | - | 13 | - |
| E | 23 | 17 | 14 | 13 | - | 21 |
| F | 22 | 20 | - | - | 21 | - |
The table shows the distances, in metres, between six vertices, A, B, C, D, E and F, in a network.
(a) Draw the weighted network using the vertices given in Diagram 1 in the answer booklet. (3)
(b) Use Kruskal’s algorithm to find a minimum spanning tree. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree. (3)
(c) Draw your tree on Diagram 2 in the answer booklet and find its total weight. (2)
| Scheme | Marks |
|---|---|
 | M1 A1 A1 |
| (3) |
Notes
(a) 1M1: More than 10 arcs
1A1: all arcs correct
2A1: all values correct
| Scheme | Marks |
|---|---|
| CD, DE, reject CE, BE, reject BC, reject BD, BF, reject EF, AF 11 13 14 17 18 19 20 21 22 | M1 A1 A1 |
| (3) |
Notes
(b) 1M1: First three arcs correctly chosen
1A1: All used acrs selected correctly
2A1: All rejected arcs selected in correct order
| Scheme | Marks |
|---|---|
 | B1 |
| Weight of tree 83 (m) | B1 |
| (2) | |
| (8 marks) |
Notes
(c) 1B1: CAO for arcs – numbers not needed. NO ft.
2B1: CAO 83, condone units