D1 June 2019 Q3
3.
| A | B | C | D | E | F | G | H | J | |
|---|---|---|---|---|---|---|---|---|---|
| A | – | 3 | 8 | 5 | – | – | – | – | – |
| B | 3 | – | 4 | – | – | – | – | – | – |
| C | 8 | 4 | – | – | 9 | 4 | – | – | – |
| D | 5 | – | – | – | – | 7 | 4 | 9 | – |
| E | – | – | 9 | – | – | 4 | – | – | 7 |
| F | – | – | 4 | 7 | 4 | – | – | 8 | 13 |
| G | – | – | – | 4 | – | – | – | 4 | – |
| H | – | – | – | 9 | – | 8 | 4 | – | 7 |
| J | – | – | – | – | 7 | 13 | – | 7 | – |
The table above shows the lengths, in metres, of the paths between nine vertices, A, B, C, D, E, F, G, H and J.
| Scheme | Marks |
|---|---|
| Prim: AB, BC, CF, EF; AD, DG; GH, EJ or HJ | M1; A1; A1 |
| Weight of tree = 35 (metres) | A1 |
 | A1 |
| (5) |
Notes
a1M1: First four arcs correctly chosen in order {AB, BC, CF, EF…} or first five nodes correctly chosen in order {A, B, C, F, E,…}. If any rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of the matrix {1, 2, 3, -, 5, 4, -, -, -} so please check the top of the matrix carefully
a1A1: First six arcs correctly chosen in order {AB, BC, CF, EF, AD, DG, …} or all nine nodes correctly chosen in order {A, B, C, F, E, D, G, H, J}. Order of nodes may be seen at the top of the matrix so for the first two marks accept {1, 2, 3, 6, 5, 4, 7, 8, 9} (do not condone any missing numbers e.g. the number 9 must be above J)
a2A1: CSO – all arcs correct stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen). Allow EJ or HJ for the final arc but not EJ and HJ
a3A1: CAO (weight of 35)
a4A1: CAO (do not award this mark if both EJ and HJ are shown in the MST)
| Scheme | Marks |
|---|---|
| No – there are two different MST (with a weight of 35) either with EJ or HJ | B1 |
| (1) |
Notes
b1B1: CAO – no (oe) + mention of two different MST with either arc EJ or HJ – as a minimum must mention EJ and HJ – or clearly implied that the final arc in the MST could be replaced with the other arc (e.g. if final arc in MST is EJ they must then say that HJ could replace the final arc in the MST) (do not award this mark if the candidate believes that unique means that there is more than one MST)
| Scheme | Marks |
|---|---|
 | M1 A1 (BDCG) A1 (FH) A1 (EJ) |
| Length of shortest path is 20 (metres) | A1ft |
| (5) | |
| 11 marks |
Notes
In (c) it is important that all values at each node are checked very carefully – the order of the working values must be correct for the corresponding A mark to be awarded and with no additional working values. It is also important that the order of labelling is checked carefully. The order of labelling must be a strictly increasing sequence – so 1, 2, 3, 3, 4, … will be penalised once (see notes below) but 1, 2, 3, 5, 6, … is fine. Errors in the final values and working values are penalised before errors in the order of labelling
c1M1: A larger value replaced by a smaller value at least once in the working values at either C or E or F or H or J
c1A1: All values at B, D, C, G correct and the working values in the correct order at C
c2A1: All values at F and H correct and the working values in the correct order at F and H
c3A1: All values at E and J correct and the working values in the correct order at E and J
c4A1ft: Follow through the value at J only