D1 June 2006 Q3
3.
Figure 2 shows the network of pipes represented by arcs. The length of each pipe, in kilometres, is shown by the number on each arc. The network is to be inspected for leakages, using the shortest route and starting and finishing at \(A\).
(a) Use the route inspection algorithm to fins which arcs, if any, need to be traversed twice. (4)
(b) State the length of the minimum route. [The total weight of the network is 394 km.] (1)
It is now permitted to start and finish the inspection at two distinct vertices.
(c) State, with a reason, which two vertices should be chosen to minimise the length of the new route. (2)
| Scheme | Marks |
|---|---|
| \(AC + EG = 44 + 35 = 79\) | M1 |
| \(AE + CG = 41 + 36 = 77\ *\) | A1 |
| \(AG + CE = 36 + 45 = 81\) | A1 |
| Repeat \(AD, DE, CF\) and \(FG\) | A1ft |
| (4) |
Notes
M1 3 pairs of their odd vertices (different)
A1 One pairing and total correct – i.e. one line correct
A1 all 3 pairings and total correct
A1ft Correct arcs identified – must be 2+ pairings to choose from
| Scheme | Marks |
|---|---|
| Length \(= 394 + 77 = 471\) km | B1ft |
| (1) |
Notes
B1 471 (km) 394 + their shortest – must be 2 pairings to choose from.
| Scheme | Marks |
|---|---|
| Since \(EG\) is the smallest choose to repeat this hence start and finish at \(A\) and \(C\). | M1 A1ft |
| (2) | |
| (7 marks) |
Notes
M1 Identifies \(EG\) (35) as smallest – or identifies their smallest from 2+ pairings & totals
A1ft from 2+ pairings + totals