The route inspection problem

The route inspection problem

Spec 3.1 · Edexcel International A Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • The route inspection problem (Chinese postman) asks for the shortest closed route that travels along every arc at least once.
  • The order (degree) of a vertex is the number of arcs meeting at it; the number of odd vertices is always even.
  • If every vertex is even, the shortest route is the total weight of all the arcs.
  • Otherwise pair up the odd vertices in every way, find the shortest path in each pair, and add the least total to the arc total.
  • Four odd vertices give three pairings; two odd vertices give one.

What the problem asks

A postal worker or gritting lorry must travel along every arc at least once and finish at the start; the aim is to repeat as little as possible.

Some jobs need every road to be travelled: a postal worker, a gritting lorry or a street cleaner. The route inspection problem, or Chinese postman problem, asks for the shortest route that travels along every arc at least once and finishes at the start vertex.

If every arc can be used exactly once, the shortest route is the sum of all the arc lengths. Otherwise some arcs must be travelled twice, and the aim is to repeat the least possible length.

w=5w=8w=4w=7w=6w=9w=3ABCDE
The street network used below

A route inspection route must...

Odd and even vertices

The order of a vertex is the number of arcs meeting at it. A closed route using each arc once needs every vertex even.

The order (degree) of a vertex is the number of arcs meeting at it. A vertex is odd or even according to its order.

A closed route using each arc once needs every vertex to be even, because each time the route enters a vertex it must leave again, using arcs in pairs.

Any network has an even number of odd vertices. Here there are 0, 2 or 4.

AB = 5AC = 8BC = 4BD = 7CD = 6CE = 9DE = 3A (2)B (3)C (4)D (3)E (2)
Schematic network (not to scale); each letter shows its order. B and D are odd, A, C and E are even.

No odd vertices

  • Route length = total weight of arcs

2 odd vertices

  • One way to pair them

4 odd vertices

  • Three ways to pair them
Cases to recognise

A network has 5 arcs. What is the sum of the orders of all its vertices?

The algorithm

Pair the odd vertices in every possible way, find the shortest path for each pair, and repeat the arcs of the pairing with the least total.

For 2 odd vertices there is one pairing. For 4 odd vertices PP, QQ, RR, SS there are 3 pairings: PQ+RSPQ+RS, PR+QSPR+QS and PS+QRPS+QR.

Find each shortest path by inspection. It may pass through other vertices.

Floyd's algorithm is not needed.

  1. 1

    List odd vertices

    find the order of every vertex

  2. 2

    None odd?

    the route length is the total weight of the arcs

  3. 3

    Pair them up

    in every possible way

  4. 4

    Shortest paths

    find the shortest path in each pair by inspection and add the lengths

  5. 5

    Choose

    take the pairing with the least total

  6. 6

    Add

    route length = total of arcs + least total

Solving a route inspection problem

How many different ways are there to pair up 4 odd vertices?

Worked example

Only B and D are odd, so repeat the shortest path between them, BD = 7, and add it to the total of the arcs.

Streets are AB=5AB=5, AC=8AC=8, BC=4BC=4, BD=7BD=7, CD=6CD=6, CE=9CE=9 and DE=3DE=3.

The orders are AA: 2, BB: 3, CC: 4, DD: 3, EE: 2, so BB and DD are the odd vertices.

There is only one pairing. The shortest path from BB to DD is BD=7BD=7, since BB-CC-DD is 10.

AB = 5AC = 8BC = 47 (repeated)CD = 6CE = 9DE = 3A (2)B (3)C (4)D (3)E (2)
Repeat the shortest path between the odd vertices B and D (BD = 7): arcs total 42, so the route is 42 + 7 = 49.
  • Total of arcs5+8+4+7+6+9+3=425+8+4+7+6+9+3=42
  • Repeat shortest path BD7
  • Route length42+7=4942+7=49

Worked example

Find the length of the shortest route that travels along every street and returns to its start.

In the example, which arc is travelled twice?

Exam skills and modifying networks

State the odd vertices, show every pairing and its total, and say which arcs are repeated; these are method marks.

The route length is always at least the total weight of the arcs, so a smaller answer shows an error.

To modify a network, add the new arc and re-do the pairing with the new odd vertices. Compare the new route length with the old one to form an inequality for the new arc's length.

The route is closed, so the length does not depend on where you start.

  1. 1

    List the odd vertices

    there are always an even number

  2. 2

    Show every pairing

    with the shortest path and total for each

  3. 3

    Choose the smallest total

    say which arcs are repeated

  4. 4

    Route length

    total weight of all arcs plus the repeated total

Route inspection: the method marks.

New arc joins two odd vertices

  • Both become even
  • Odd vertices fall by 2

New arc joins odd to even

  • Even vertex becomes odd
  • Number of odd vertices unchanged
Effect of adding an arc

A new arc joins two vertices that are both odd. How many odd vertices are there now, if there were 4 before?

Try an exam question

A network has arcs PQ = 10, PR = 5, QR = 6, QS = 9, RS = 7 and ST = 4. Find the length of the shortest route that travels along every arc at least once and returns to its start. Show the pairings you considered.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

How many junctions have an odd number of streets meeting at them?

1 mark, marked against the mark scheme

Revision notes