D1 January 2007 Q5
5.
(a) Explain why a network cannot have an odd number of vertices of odd degree. (2)
Figure 4 shows a network of paths in a public park. The number on each arc represents the length of that path in metres. Hamish needs to walk along each path at least once to check the paths for frost damage starting and finishing at \(A\). He wishes to minimise the total distance he walks.
(b) Use the route inspection algorithm to find which paths, if any, need to be traversed twice. (4)
(c) Find the length of Hamish’s route.
[The total weight of the network in Figure 4 is 4180 m.] (1)
[The total weight of the network in Figure 4 is 4180 m.] (1)
| Scheme | Marks |
|---|---|
| e.g. Each edge contributes 2 to the sum of degrees, hence this sum must be even. Therefore there must be an even (or zero) number of vertices of odd degree Hence there cannot be an odd number of vertices of odd degree | B2,1,0 |
| (2) |
| Scheme | Marks |
|---|---|
| \(CD + FH = 200 + 220 = 420\ *\) | M1 A1 |
| \(CF + DH = 180 + 380 = 560\) | A1 |
| \(CH + DF = 400 + 160 = 560\) | |
| repeat \(CA, AD\) and \(FH\) | A1 |
| (4) |
| Scheme | Marks |
|---|---|
| length \(= 4180 + 420\)ft \(= 4600\) m | B1ft |
| (1) | |
| (7 marks) |