AS June 2022 Q3
3.
[The total weight of the network is 120]
Figure 2 represents a network of cycle tracks between eight villages, A, B, C, D, E, F, G and H. The number on each arc represents the length, in km, of the corresponding track. Samira lives in village A, and wishes to visit her friend, Daisy, who lives in village H.
An extra cycle track of length 9 km is to be added to the network. It will either go directly between C and D or directly between E and G.
Daisy plans to cycle along every track in the new network, starting and finishing at H.
Given that the addition of either track CD or track EG will not affect the final values obtained in (c),
- state which tracks Daisy will repeat in her route
- state the total length of her route
| Scheme | Marks | AO |
|---|---|---|
| A path is a (i) finite sequence of edges, such that (ii) the end vertex of one edge in the sequence is the start vertex of the next, and in which (iii) no vertex appears more than once | B2,1,0 | 1.2 1.2 |
| (2) |
Notes
B1: One of the three points made clearly (‘finite, edges’, ‘end vertex of one edge is the start vertex of the next’, ‘no vertex appears more than once’ – condone ‘a vertex cannot appear twice’ but not ‘a vertex cannot be repeated more than once’)
B1: All three points made clearly. Candidates who state that a path is a walk in which no vertex appears more than once can score B1B0 only
| Scheme | Marks | AO |
|---|---|---|
| Graph is neither Eulerian nor semi-Eulerian because it has six odd vertices. | B1 | 2.4 |
| (1) |
Notes
B1: Correct statement (neither) with correct reason. Either states that there are more than two odd nodes or does not have exactly zero or two odd nodes or that there are six odd nodes. Their argument must be convincing that the graph cannot be Eulerian or semi-Eulerian (e.g. ‘the network does not have two odd nodes’ is B0). Do not ISW (or BOD) if any incorrect reasoning given
| Scheme | Marks | AO |
|---|---|---|
 | M1 A1 (ABDC) A1 (FE) A1ft (GH) | 1.1b 1.1b 1.1b 1.1b |
| Shortest path: ABEH | A1 | 2.2a |
| (5) |
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 e.g. at H the working values must be 24 22 in that order (so 22 24 is incorrect)
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
M1: A larger value replaced by a smaller value at least twice in the working values at either C, F, G, H
A1: All values at A, B, D and C correct and the working values in the correct order
A1: All values at F and E correct and working values in the correct order. Penalise order of labelling only once per question. Condone an additional working value of 18 after the 17 at E
A1ft: All values in G and H correct on the follow through and the working values in the correct order. To follow through G check that the working values at G follow from the candidate’s final values for the nodes that are directly attached to G (which are D and F). For example, if correct then the order of labelling of nodes D and F are 3 and 5 respectively so the working values at G should come from D and F in that order. The first working value at G should be their 10 (the Final value at D) + 11 (the weight of the arc DG), the second working value at G should be their 14 (the Final value at F) + 6 (the weight of the arc FG). Repeat the process for H (which will have working values from F, E and G with the order of these nodes determined by the candidate’s order of labelling at F, E and G). Condone an additional working value of 32 after the 22 at H
A1: cao for shortest path (ABEH)
| Scheme | Marks | AO |
|---|---|---|
| If arc CD included: AE + GH = 17 + 12 = 29 AG + EH = 20 + 5 = 25 AH + EG = 22 + 10 = 32 | M1 A1 | 3.1b 1.1b |
| If arc EG included: AC + DH = 11 + 17 = 28 AD + CH = 10 + 12 = 22* AH + CD = 22 + 11 = 33 | depM1 A1 | 1.1b 1.1b |
| Track EG with repeated arcs AD, CF, FE, EH Length = 120 + 9 + 22 = 151 (km) | A1 A1 | 2.2a 2.2a |
| (6) | ||
| (14 marks) |
Notes
M1: One correct set (either AEGH or ACDH) of three distinct pairings of the correct four odd nodes (so must have AE + GH, AG + EH and AH + EG or AC + DH, AD + CH and AH + CD)
A1: Any three rows correct including pairings and totals, from either set AEGH or set ACDH
dM1: All six distinct pairings for nodes AEGH and ACDH – dependent on first M mark
A1: All six rows correct including pairings and totals
A1: cao correct edges clearly stated and not just in their working. Must be edges AD, CF, FE, EH and clearly selecting track EG
A1: cao (151) from correct working – dependent on first four marks in this part