The Route Inspection (Chinese Postman) problem
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.
- Sum of degrees 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:
- Identify the odd vertices.
- List every pairing of them.
- For each pairing, find the shortest path joining each pair and add the weights.
- Choose the pairing with the least total.
- 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
Find odd vertices
list the degrees
- 2
List pairings
every way to pair them up
- 3
Add shortest paths
total for each pairing
- 4
Choose the least
the smallest pairing total
- 5
Add to the total
network weight plus that total
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.
Worked example
The total weight is 36 and the only odd vertices are and . The direct arc is 7, but there is also a path with and . Find the shortest route.
- 1
There is one pairing, with .
- 2
The direct arc is 7, but is , which is shorter.
- 3
Repeat .
Total weight 50. The only odd vertices are and . The direct arc is 9, and has length . 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.
| BC and EF | BE and CF | BF and CE | |
|---|---|---|---|
| Working | 6 + 5 | 12 + 11 | 17 + 16 |
| Total | 11 | 23 | 33 |
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 , , and . Find the length of the shortest route.
- 1
The odd vertices are , , and .
- 2
Pairings: ; ; .
- 3
The least is 11, so arcs and are repeated.
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 , , and with shortest distances , , , , , . Find the length of the shortest closed route that uses every arc.
[4 marks]
- [1]Identifies the three pairings , and .
- [1]Totals are 13, 23 and 14.
- [1]The least is 13, so the shortest paths and are repeated.
- [1]Length of shortest route is .
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
Which vertices have odd degree?
1 mark, marked against the mark scheme