Route Inspection | Edexcel A Level Further Maths: Decision Maths 1 Revision Notes 2017

Chinese Postman Problem

The route inspection problem is also known as the Chinese postman problem
You are required to find the route of least weight that traverses every edge in the graph such that the route starts and finishes at the same vertex
Some edges may need to be traversed twice and the challenge is to minimise the total weight of these repeated edges
Variations to the route inspection problem could involve
- the start and finish vertices being different
- certain edges being disregarded
  - e.g. a road closure
- the route requiring repetition
  - e.g. a road sweeper covering both sides of the road

STEP 1
Inspect the degree of all of the vertices and identify any odd nodes
STEP 2
If all of the vertices are even go to STEP 3
If there is one pair of odd nodes, find the shortest path between them - the edges making this path will need repeating so add them to the graph
STEP 3
Write down an Eulerian circuit of the adjusted graph to find a possible route
- Find the sum of the edges traversed to find the total weight

Look carefully for the shortest path between two vertices
- exam questions often have graphs where a path made up of several edges will create a shorter distance than a direct connection

The network shown below displays the distance, in metres, of the cables in a network between different connection points A, B, C, D, E and F.

Each length of cable must be inspected.

jv2R5V-u_chinese-postman

Find the shortest route that starts and finishes at connection point E.

A: 5 (odd)
B: 2 (even)
C: 3 (odd)
D: 2 (even)
E: 4 (even)
F: 2 (even)

STEP 2
There is exactly one pair of odd vertices, A and C
The shortest route between A and C is ABC so the edges AB and BC need repeating
An Eulerian circuit, starting and ending at connection point E, is now possible
STEP 3
Find an Eulerian circuit, starting and ending at connection point E

Shortest route: EFAEDABACBCE

State the total length of the shortest route.

Add together the lengths of the edges in the original graph

3 + 4 + 4 + 5 + 8 + 9 + 11 + 13 + 16 = 73

Add the result to the lengths of the repeated edges

73 + 5 + 9 = 87

Shortest route = 87 km