D1 June 2007 Q5
5.
| M | A | B | C | D | E | |
|---|---|---|---|---|---|---|
| M | – | 215 | 170 | 290 | 210 | 305 |
| A | 215 | – | 275 | 100 | 217 | 214 |
| B | 170 | 275 | – | 267 | 230 | 200 |
| C | 290 | 100 | 267 | – | 180 | 220 |
| D | 210 | 217 | 230 | 180 | – | 245 |
| E | 305 | 214 | 200 | 220 | 245 | – |
The table shows the cost, in pounds, of linking five automatic alarm sensors, A,B,C,D and E, and the main reception, M.
(a) Use Prim’s algorithm, starting from M, to find a minimum spanning tree for this table of costs. You must list the arcs that form your tree in the order that they are selected. (3)
(b) Draw your tree using the vertices given in Diagram 1 in the answer book. (1)
(c) Find the total weight of your tree. (1)
(d) Explain why it is not necessary to check for cycles when using Prim’s algorithm. (2)
| Scheme | Marks |
|---|---|
| MB, BE, MD, DC, CA | M1 A1 A1 |
| (3) |
| Scheme | Marks |
|---|---|
 | B1ft |
| (1) |
| Scheme | Marks |
|---|---|
| 170 + 200 + 210 + 180 + 100 = 860 | B1 |
| (1) |
| Scheme | Marks |
|---|---|
| (A cycle is formed when an arc is used that connects two vertices already connected to each other in the tree) Prim’s algorithm always selects arcs that bring a vertex not in the tree into the tree, so cycles can’t happen | B2, 1, 0 |
| (2) | |
| (7 marks) |