D1 June 2015 Q4
4.
[The total weight of the network is 2090]
Figure 4 represents a network of 13 roads in a village. The number on each arc is the length, in metres, of the corresponding road. A route of minimum length that traverses each road at least once needs to be found. The route may start at any vertex and finish at any vertex.
A new road, AB, of length 130m is built. A route of minimum length that traverses each road, including AB, needs to be found. The route must start and finish at A.
It is now decided to start and finish the inspection route at two distinct vertices. A route of minimum length that traverses each road, including AB, needs to be found. The route must start at A.
| Scheme | Marks |
|---|---|
| e.g. (each arc contributes 1 to the orders of two nodes, and so) the sum of the orders of all the nodes is equal to twice the number of arcs | B1 |
| Which implies that the sum of the orders of all the nodes is even and therefore there must be an even (or zero) number of vertices of odd order hence there cannot be an odd number of vertices of odd order. | B1 |
| (2) |
Notes
a1B1: Either stating that the sum of the order of the nodes = 2(number of arcs) or that each arc contributes 1 to the order of two nodes. For this mark there must be a clear correct statement linking the order of nodes to arcs
a2B1: For stating that as the sum (of the orders) of the nodes is even this implies that there must be an even number of nodes of odd order (or there cannot be an odd number of nodes of odd order). Candidates may argue that if the sum (of the order) of the nodes is odd then this implies that the number of arcs cannot be integer valued (oe) which is fine. For this mark there must be a correct statement that the sum of the nodes is even together with the correct conclusion. Note that for the first B mark it must be clear that the candidate is considering the order of the nodes but for the second B mark it is sufficient to for candidates to say ‘the sum of the nodes…’. Furthermore, it is possible to score B0B1 (for example, a candidate may simply state the sum of the nodes is even and state the correct conclusion which would score the 2nd B mark only)
| Scheme | Marks |
|---|---|
| (Start at) D and (end at) E (or vice-versa) | B1 |
| (1) |
Notes
b1B1: Correct start and finish points (D, E)
| Scheme | Marks |
|---|---|
| A(C)B + D(BC)E = 120 + 300 = 420 | M1 |
| A(CB)D + B(C)E = 290 + 130 = 420 | A1 (2 rows) |
| A(C)E + BD = 150 + 170 = 320* | A1 (3 rows) |
| Repeat arcs AC, CE and BD | A1 |
| (4) |
Notes
c1M1: Three distinct pairings of the correct four odd nodes
c1A1: Any two rows correct including pairings and totals
c2A1: All three rows correct including pairings and totals
c3A1: CAO correct arcs clearly (not just in their working) stated: AC, CE, BD. Accept ACE or AE via C. Do not accept AE
| Scheme | Marks |
|---|---|
| Length 2090 + 320 + 130 = 2540 (m) | M1, A1 |
| (2) |
Notes
d1M1: 2090 + 130 + (their smallest total from (c)); must be at least two distinct pairings of the correct four odd nodes in (c) or for 2410 only (forgetting to add the additional 130)
d1A1: CAO (2540) – if no working seen then the correct answer implies both marks in (d)
| Scheme | Marks |
|---|---|
| (Finishing Point is) D | B1 |
| Difference in routes = 2540 – (2090 + 130 +130 ) = 190 (m) | M1, A1 |
| (3) | |
| (12 marks) |
Notes
e1B1: CAO (D)
e1M1: Their answer to (d) – (2090 + 130 + their BE) (if AB included in (d)) or their answer to (d) – (2090 + their BE) (if AB not included in (d)) or (their smallest total (320) from (c) – their BE (130)) – by ‘their BE’ this is their smallest pairing which does not include A. This mark is dependent on either scoring the M mark in (c) or considering all three pairings (DE, BE, BD) that do not include A
e1A1: CAO (190) – condone lack of units – if the correct answer is seen with no calculation and/or method seen then award the M mark only. Candidates who did not include AB (130) in their inspection route (in (d)) can still earn full marks in (e) for the correct answer of 190