The Route Inspection (Chinese Postman) problem

The Route Inspection (Chinese Postman) problem

Spec 3.1 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • The Route Inspection problem finds the shortest closed route that uses every arc at least once.
  • A vertex is odd if its degree is odd. Every network has an even number of odd vertices.
  • If all vertices are even the network is Eulerian and the route is the total weight.
  • Otherwise pair the odd vertices, repeat the shortest paths for the best pairing and add them to the total.
  • Two odd vertices have one pairing; four odd vertices have three pairings.

Why degrees matter

If every vertex has even degree, you can use every arc once and return to the start, so the shortest route is the total weight.

The degree 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: each arc can be used exactly once and the route ends at the start.

A (3)B (2)C (3)D (2)
Degrees: A and C are odd (3), B and D are even (2). The degrees add to 10 = 2 × 5 arcs, and there are 2 odd vertices, an even number.
  • Sum of degrees2×2\times number of arcs

A network has six vertices with degrees 3, 3, 4, 2, 5 and 3. How many odd vertices does it have?

The algorithm

Pair up the odd vertices, find the pairing with the least total of shortest paths, and repeat those arcs.

If there are odd vertices, some arcs must be travelled twice. The Route Inspection Algorithm is:

  1. Identify the odd vertices.
  2. List every pairing of them.
  3. For each pairing, find the shortest path joining each pair and add the weights.
  4. Choose the pairing with the least total.
  5. Repeat the arcs on those paths. The route length is the network's total weight plus that least total.

The repeated arcs make every vertex even.

  1. 1

    Find odd vertices

    list the degrees

  2. 2

    List pairings

    every way to pair them up

  3. 3

    Add shortest paths

    total for each pairing

  4. 4

    Choose the least

    the smallest pairing total

  5. 5

    Add to the total

    network weight plus that total

Route Inspection Algorithm

After the arcs of the best pairing are repeated, what is true of every vertex?

Two odd vertices

There is one pairing, so repeat the shortest path between them. It may not be the direct arc.

With exactly two odd vertices there is only one pairing, so the extra length is the shortest path between them.

Check all the alternative paths before you decide, especially when the direct arc is long.

BD 7BC 2CD 4BCD
The direct arc BD is longer than the path B-C-D.

Worked example

The total weight is 36 and the only odd vertices are BB and DD. The direct arc BDBD is 7, but there is also a path B−C−DB-C-D with BC=2BC=2 and CD=4CD=4. Find the shortest route.

Total weight 50. The only odd vertices are PP and QQ. The direct arc PQPQ is 9, and P−R−QP-R-Q has length 3+43+4. What is the shortest route?

Four odd vertices

Four odd vertices give three pairings. Find the shortest path for each pair, total each pairing and choose the least.

With four odd vertices P, Q, R and S the three pairings are PQ with RS, PR with QS, and PS with QR. Choose the least total.

The Edexcel specification allows at most four odd vertices. If the network is changed, such as by adding an arc, recount the degrees because the odd vertices may change.

To write out the route, list the vertices in order, with each repeated arc appearing twice.

05101520253035BC and EFBE and CFBF and CEPairingTotal
Total weight of each pairing of the odd vertices B, C, E, F: the least (11) is repeated.

BC and EF

Working:
6 + 5
Total:
11

BE and CF

Working:
12 + 11
Total:
23

BF and CE

Working:
17 + 16
Total:
33

Worked example

A network has total weight 68 and odd vertices BB, CC, EE and FF. Find the length of the shortest route.

A network has total weight 52 and the three pairings of its odd vertices have totals 9, 14 and 11. What is the length of the shortest route?

Try an exam question

A network has total weight 94. Its odd vertices are AA, BB, CC and DD with shortest distances AB=7AB=7, AC=12AC=12, AD=9AD=9, BC=5BC=5, BD=11BD=11, CD=6CD=6. Find the length of the shortest closed route that uses every arc.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which vertices have odd degree?

1 mark, marked against the mark scheme

Revision notes