Route Inspection (Edexcel International A Level Maths): Revision Note

The Chinese Postman Problem

What is the 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 a graph

  • The route must start and finish at the same vertex

• Some edges may need to be traversed more than once

  • 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

  • Repetition being required on the route

    • E.g. a road sweeper covering both sides of the road

Networks with 0 or 2 Odd Vertices

How do I solve the Chinese postman problem in networks with 0 or 2 Odd Vertices?

• If the graph is Eulerian

  • All of the vertices in the graph are even

    • I.e. there are 0 odd nodes

  • It will be possible to find an Eulerian circuit

    • I.e. a route that traverses each edge exactly once, starting and finishing at the same vertex

  • No route or edges will need repetition 

  • The shortest route will be the sum of the weights of the edges in the network

• If the graph is semi-Eulerian

  • There will be one pair of odd vertices
    

    • I.e. there will be 2 odd nodes

  • If the route has to start and end at the same vertex

    • The shortest path between the two odd nodes will need to be found

    • The edges making that shortest path will need to be repeated

    • The shortest route will be the sum of the weights of the edges in the network plus the weight of the repeated edges

  • If the route starts at one of the odd vertices and ends at the other

    • No path/edges will need repetition

    • The shortest route will be the sum of the weights of the edges in the network

What are the steps of the Chinese postman algorithm?

• 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 to be repeated so add them to the graph
  (Once they are added to the graph every node will be even, so an Eulerian circuit will exist)
    

• 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