AS June 2023 Q5
5.
[The weight of the network is \(20x + 3\)]
Figure 4 shows a graph G that contains 8 arcs and 6 vertices.
Figure 4 represents a network of 8 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
You are given that \(x \gt 1.6\)
A route is required that
- starts and finishes at the same vertex
- traverses each road at least once
- minimises the total time taken
The route inspection algorithm is applied to the network in Figure 4 and the time taken for the route is found to be at most 189 minutes.
Given that the inspection route contains two roads that need to be traversed twice,
| Scheme | Marks | AO |
|---|---|---|
| 1 | B1 | 1.2 |
| (1) |
Notes
(a) B1: cao
| Scheme | Marks | AO |
|---|---|---|
| The route is not an example of a path as vertex C appears twice | B1 | 2.4 |
| (1) |
Notes
(b) B1: No + correct reason – no bod – must refer to C appearing twice (not just that a vertex is repeated) or that it contains the cycle C – F – E – C (not just that it contains a cycle). All technical language must be correct if used for this mark and do not isw any incorrect reasoning (for example if they imply that a path must pass through every vertex)
| Scheme | Marks | AO |
|---|---|---|
| As the route contains two roads that need to be traversed twice this means that either the pairing AB, AC or BD, CD needs to be repeated | B1 | 2.1 |
| AB + AC = \(3x + 6\) and BD + CD = \(3x + 2\) and as \(3x + 6 \gt 3x + 2\) (for all values of \(x\)) this means that BD + CD are repeated | B1 | 2.2a |
| Because two roads are repeated in the shortest inspection route this means that \(5x - 8 \gt 3x + 2\) | M1 | 3.1b |
| \(x \gt 5\) | A1 | 1.1b |
| \((20x + 3) + (3x + 2) \leqslant 189\) | M1 | 3.4 |
| \(x \leqslant 8\) | A1 | 2.2a |
| (6) | ||
| (8 marks) |
Notes
(c) B1: Recognising that one of the two pairings between B and C containing two arcs will need to be repeated. For example, might state BAC or BDC or BA, AC or BD, DC (as an indication of considering the two odd nodes B and C together with one of the two paths via A and D) or one of the expressions \(3x + 6\) or \(3x + 2\) (or correct but unsimplified) seen would score this mark. Condone for this mark those candidates who consider the direct arc BC (provided at least one of the pairings via A or D is considered too)
B1: Correct deduction that BD + CD needs to be repeated (or that AB + AC is not repeated). Allow stating that \(3x + 2\) is ‘better’ than \(3x + 6\) or simply stating both expressions and selecting \(3x + 2\) (but we must see both simplified expressions for this mark). This selection of \(3x + 2\) (after seeing both expressions) could be implied by forming an equation/inequality with only this expression. This mark cannot be awarded if either of the other two inequalities/equations e.g. \((20x + 3) + (3x + 6) \leqslant 189\) or \((20x + 3) + (5x - 8) \leqslant 189\) are formed, unless they are explicitly rejected with the correct reason (that is because \(3x + 6 \gt 3x + 2\) and because the route contains two roads). Obtaining \(x \leqslant 7.826\ldots\) and/or \(x \leqslant 7.76\) and simply rejecting these without the valid reasons as stated above does not score this mark
M1: Considers explicitly the direct route between B and C (\(5x - 8\)) and compares this (in the form of a linear equation or inequality) with either of the two pairings AB + AC or BD + CD
A1: cao (\(x \gt 5\))
M1: (\(20x + 3\)) + (either their \(3x + 6\) or their \(3x + 2\)) together with 189 (allow equals or any inequality)
A1: cao (\(x \leqslant 8\))
If full marks would have been awarded in (c) but any other inequalities apart from \(x \gt 5\) and \(x \leqslant 8\) are found, then withhold the second B mark