All revision notes topics

The Route Inspection (Chinese Postman) problemEdexcel A-Level Further Maths: Revision notes

Section 1

The problem and why degrees matter

The Route Inspection problem asks for the shortest closed route that travels along every arc of a network at least once and ends at the start vertex. Examples are a postman delivering to every street or a council inspecting every road. The degree (or order) of a vertex is the number of arc-ends meeting there. A vertex is odd if its degree is odd and even otherwise. Every network has an even number of odd vertices, because the degrees add up to twice the number of arcs. If every vertex is even, the network is Eulerian: you can traverse each arc exactly once and return to the start, so the shortest route is just the total weight of all the arcs.

Key termsdegreeodd vertexEulerian
Common mistake

Counting the degree wrongly. List the arcs at each vertex before deciding which are odd, and check there is an even number of odd vertices.

Section 2

The algorithm

If the network has odd vertices, some arcs must be travelled twice. The Route Inspection Algorithm is:

  1. Identify all the odd vertices.
  2. List every way of pairing them up.
  3. For each pairing, find the shortest path joining the two vertices of each pair and add up the weights.
  4. Choose the pairing with the least total.
  5. Repeat the arcs on those shortest paths. The route length is the total weight of the network plus that least total. The repeated arcs make every vertex even, so an Eulerian route now exists.
Key termsRoute Inspection Algorithmpairing
Exam tip

State the pairings you tried and their totals. Marks are given for showing all of them, not just the best.

Section 3

Two odd vertices

With exactly two odd vertices there is only one pairing, so the extra length is the shortest path between them. That path may not be the direct arc. Example: the total weight is 36 and the only odd vertices are B and D. The direct arc BD is 7, but B–C–D is 2 + 4 = 6. Repeat B–C–D, so the shortest route is 36 + 6 = 42. Check all the alternative paths between the two vertices before you decide, especially when the direct arc is long.

Key termsshortest path
Common mistake

Adding the direct arc between the two odd vertices without checking that an indirect path is shorter.

Section 4

Four odd vertices

With four odd vertices P, Q, R and S there are three pairings: PQ with RS, PR with QS, and PS with QR. Work out the shortest path for each pair, add the two shortest paths for each pairing and choose the least total. Example: for odd vertices B, C, E and F the pairings give 6 + 5 = 11, 12 + 11 = 23 and 17 + 16 = 33. The least is 11, so repeat arcs BC and EF. The Edexcel specification allows at most four odd vertices. If a network has more, the question gives extra information that limits the pairings to consider, for example by saying which vertices may be paired.

Key termsfour odd vertices
Exam tip

Use inspection: write the three pairings as a short list, then fill in the shortest distance for each pair.

Section 5

Writing out a full solution

Worked example. A network has total weight 68 and odd vertices B, C, E and F.

  1. The odd vertices are B, C, E and F (degrees 3).
  2. Pairings: BC + EF = 11; BE + CF = 23; BF + CE = 33.
  3. The least is 11, so arcs BC and EF are repeated.
  4. The length of the shortest route is 68 + 11 = 79. When asked for the route itself, list the vertices in order and make sure each repeated arc appears twice. If the question changes the network, such as adding a new arc, recount the degrees, because the odd vertices may change.
Key termsrepeated arcs
Common mistake

Forgetting to add the total weight of the network. The answer is the total plus the repeated arcs, not the repeated arcs alone.

That's the notes covered.

Carry on to the next subtopic.

Exam questions on The Route Inspection (Chinese Postman) problem

  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.
    Find the length of the shortest route that starts and ends at A and uses every arc at least once.2 marks
  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.
    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
  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.
    Find the length of the shortest inspection route.3 marks
See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).