D1 June 2009 Q1
1.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | - | 135 | 180 | 70 | 95 | 225 |
| B | 135 | - | 215 | 125 | 205 | 240 |
| C | 180 | 215 | - | 150 | 165 | 155 |
| D | 70 | 125 | 150 | - | 100 | 195 |
| E | 95 | 205 | 165 | 100 | - | 215 |
| F | 225 | 240 | 155 | 195 | 215 | - |
The table shows the lengths, in km, of potential rail routes between six towns, A, B, C, D, E and F.
(a) Use Prim’s algorithm, starting from A, to find a minimum spanning tree for this table. 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) State the total weight of your tree. (1)
| Scheme | Marks |
|---|---|
| AD, AE, DB; DC, CF | M1 A1; A1 |
| (3) |
Notes
(a) 1M1: Using Prim – first 2 arcs probably but condone starting from another vertex.
1A1: first three arcs correct
2A1: all correct.
Apply the misread rule, if not listing arcs or not starting at A.
So for M1 (only)
Accept numbers across the top (condoning absence of 6)
Accept full vertex listing
Accept full arc listing starting from vertex other than A
| [AD AE DB DC CF] | {1 4 5 2 3 6} | ADEBCF |
| BD AD AE CD CF | {3 1 5 2 4 6} | BDAECF |
| CD AD AE BD CF | {3 5 1 2 4 6} | CDAEBF |
| DA AE DB CD CF | {2 4 5 1 3 6} | DAEBCF |
| EA AD DB DC CF | {2 4 5 3 1 6} | EADBCF |
| FC CD AD AE BD | {4 6 2 3 5 1} | FCDAEB |
| Scheme | Marks |
|---|---|
 | B1 |
| (1) |
Notes
(b) 1B1: CAO
| Scheme | Marks |
|---|---|
| Weight 595 (km) | B1 |
| (1) | |
| (5 marks) |
Notes
(c) 1B1: CAO condone lack of km.