AS October 2020 Q3
3.
[The weight of the network is \(5x + 246\)]
Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
Prim’s algorithm, starting at A, is applied to the network. The order in which the arcs are selected is AD, DH, DG, FG, EF, CG, BD. It is given that the order in which the arcs are selected is unique.
A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex.
Given that the time taken to traverse this route is 318 minutes,
| Scheme | Marks | AO |
|---|---|---|
| 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 | 1.2 |
| 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 | B1dep | 2.4 |
| (2) |
Notes
B1: For one of the following points:
- ‘Sum of the order/valencies of the nodes/vertices = 2(number of arcs/edges)’
- ‘Each arc/edge contributes 1 to the order/valency of two nodes/vertices’
- ‘Sum of the order/valencies of the nodes/vertices is even’
But condone for B1 only
- ‘sum of the valencies = 2(number of arcs/edges)’ or ‘sum of the nodes/vertices = 2(number of arcs/edges)’ or ‘sum of the orders = 2(number of arcs/edges)
- ‘sum of the valencies is even’ or ‘sum of the nodes/edges is even’
B1dep: Stating that ‘the sum of the order (or valencies) of the nodes/vertices = 2(number of arcs/edges) therefore the sum of the order (of the nodes/vertices) is even which implies that there must be an even number of nodes/vertices of odd order (or there cannot be an odd number of nodes/vertices of odd order) OR each arc/edge contributes 1 to the order of two nodes/vertices therefore the sum of the order (of the nodes/vertices) is even which implies that there must be an even number of nodes/vertices of odd order (or there cannot be an odd number of nodes/vertices of odd order)
So in summary the first B mark should be awarded for a broadly correct statement (but allow bod as shown in the last two bullet-points above) but for both B marks a fully correct explanation must be given without any bod (please note therefore it is not possible to score B0B1). Do not accept non-technical language for nodes/arcs for either B1B0 or B1B1
| Scheme | Marks | AO |
|---|---|---|
| Either \(2x + 10 > 3x - 2\) or \(2x + 10 > 20\) | M1 | 3.1b |
| \(x < 12\) | A1 | 1.1b |
| \(x > 5\) | A1 | 1.1b |
| (3) |
Notes
M1: Either comparing arc AB with AD or BD with AB – accept any inequality symbol or equals
A1: CAO (\(x < 12\))
A1: CAO (\(x > 5\))
| Scheme | Marks | AO |
|---|---|---|
| Applies the route inspection algorithm to this non-standard case | M1 | 3.1b |
| C(GF)E + F(GD)H = 37 + 25 = 62 | A1 | 1.1b |
| C(G)F + E(FGD)H = 25 + 37 = 62 | A1 | 1.1b |
| C(GD)H + EF = 30 + 12 = 42* | A1 | 1.1b |
| \(5x + 246 + 42 = 318\) | M1dep | 3.1a |
| \(x = 6\) | A1 | 2.2a |
| (6) | ||
| (11 marks) |
Notes
M1: Correct three pairings of the required four odd nodes (C, E, F and H)
A1: Any one correct pairing and total
A1: Any two correct pairings and totals
A1: All three correct pairings and totals
M1dep: Setting up an equation using the given values and their smallest pairing (dependent on the previous M mark) – must have three totals from application of route inspection
A1: CAO (\(x = 6\))