Edexcel A-Level Further Maths
The Route Inspection (Chinese Postman) problem
Total 27 marks
Name
Class
Date
- 1A network has vertices A, B, C, D and E. The arcs and their weights are: AB 5, AC 7, BC 4, BD 6, CD 3, CE 8 and DE 5.(a)Which vertices have odd degree?[1 mark]
- AA and E
- BB and D
- CC only
- DB, C and D
Show the mark scheme
Mark scheme
Answer: B(b)What is the total weight of all the arcs?[1 mark]- A32
- B44
- C38
- D76
Show the mark scheme
Mark scheme
Answer: C(c)Find the length of the shortest route that starts and ends at A and uses every arc at least once.[2 marks]Show the mark scheme
Mark scheme
M1: pair the odd vertices B and D, adding the shortest path between them, 6 (arc BD; B–C–D is longer at 7)
A1: 44
Accept: 38 + 6Total for question 1: 4 marks
- 2A network has vertices A, B, C, D, E and F. The arcs and their weights are: AB 8, BC 6, CD 9, DE 7, EF 5, FA 10, BE 12 and CF 11.(a)The network has four odd vertices. In how many different ways can these four vertices be split into two pairs?[1 mark]
- A3
- B4
- C6
- D2
Show the mark scheme
Mark scheme
Answer: A(b)What is the least total weight that must be added by repeating arcs so that the network can be traversed from A and back to A?[1 mark]- A23
- B33
- C17
- D11
Show the mark scheme
Mark scheme
Answer: D(c)State which arcs are repeated and find the length of the shortest route that starts and ends at A and uses every arc at least once.[2 marks]Show the mark scheme
Mark scheme
M1: repeat arcs BC and EF (pairing B with C and E with F)
A1: 79
Accept: 68 + 11Total for question 2: 4 marks
- 3A council must inspect every road in a village. The junctions are A, B, C, D, E and F and the road lengths in km are: AB 3, AC 5, BC 2, BD 7, CD 4, CE 7, DF 5 and EF 3. The inspector starts and finishes at junction A.(a)Find the length of the shortest inspection route.[3 marks]
Show the mark scheme
Mark scheme
B1: odd vertices are B and D
M1: shortest path from B to D is B–C–D = 2 + 4 = 6, which is less than the direct road BD = 7
A1: 42 km
Accept: 36 + 6
Do not accept: 43 (using the direct road BD)(b)A new road CF of length 3 km is built. Find the new length of the shortest inspection route.[4 marks]Show the mark scheme
Mark scheme
B1: odd vertices are now B, C, D and F
M1: considers the three pairings, BC + DF = 2 + 5 = 7, BD + CF = 6 + 3 = 9 and BF + CD = 5 + 4 = 9
A1: least is 7, repeating BC and DF
A1: 39 + 7 = 46 kmTotal for question 3: 7 marks
- 4A park warden must walk along every path in a nature reserve, starting and finishing at the car park A. The path junctions are A, B, C, D, E and F, and the path lengths, in hundreds of metres, are: AB 4, BC 7, CD 5, DE 6, EF 3, FA 8 and BE 20.(a)(i) Identify the odd vertices.[6 marks]
(ii) Find the shortest path between the odd vertices.
(iii) Hence find the length of the warden's shortest route and state which paths are walked twice.Show the mark scheme
Mark scheme
B1: (i) B and E are odd (degree 3); A, C, D and F are even
M1: (ii) compares paths from B to E: BE = 20, B–A–F–E = 15, B–C–D–E = 18
A1: (ii) shortest is B–A–F–E = 15
M1: (iii) total of all paths 53 plus 15
A1: (iii) 68 (hundred metres), which is 6800 m
B1: (iii) paths AB, AF and FE are walked twice(b)A new path CE of length 4 is built. Find the new length of the shortest route and decide whether building the path shortens the warden's walk. Justify your answer.[6 marks]Show the mark scheme
Mark scheme
B1: C and E now have degree 3 and 4, so the odd vertices are B and C
M1: compares paths from B to C: BC = 7, B–A–F–E–C = 19, B–E–C = 24
A1: shortest is BC = 7
M1: new total 53 + 4 = 57, then add 7
A1: 64 (hundred metres)
R1: 64 < 68, so the new path shortens the walk by 4 hundred metres (400 m)Total for question 4: 12 marks
End of questions