The Route Inspection (Chinese Postman) problem

The Route Inspection (Chinese Postman) problem Test

Spec 3.1 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

The Route Inspection (Chinese Postman) problem

Total 27 marks

Name

Class

Date

  1. 1
    A 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 + 6

    Total for question 1: 4 marks

  2. 2
    A 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 + 11

    Total for question 2: 4 marks

  3. 3
    A 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 km

    Total for question 3: 7 marks

  4. 4
    A 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.
    (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.
    [6 marks]
    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

Subtopic tests