Chinese Postman Problem (DP IB Applications & Interpretation (AI)): Revision Note

Eulerian trails & circuits

What are Eulerian trails and circuits?

• An Eulerian trail is a trail that visits each edge in a graph exactly once

• An Eulerian circuit is a trail that visits each edge in a graph exactly once and begins and ends at the same vertex

• A graph which contains an Eulerian circuit is called an Eulerian graph

  • In an Eulerian graph the degree of each vertex is even

• A semi-Eulerian graph contains an Eulerian trail but not an Eulerian circuit

  • In a semi-Eulerian graph exactly one pair of vertices have an odd degree

    • These are the start and finish points of any Eulerian trail

Chinese postman problem

What is the Chinese postman problem?

• The Chinese postman problem requires you to find the route of least weight such that

  • it starts and finishes at the same vertex

  • and it traverses every edge in the graph at least once

• Some edges may need to be traversed twice and the challenge is to minimise the total weight of these repeated edges

How do I solve the Chinese postman problem?

• Inspect the degree of all the vertices and identify any odd vertices

If all the vertices in the graph are even

• Any Eulerian circuit solves the problem

• The length of the shortest route is the sum of the weights of the edges in the graph

If there is one pair of odd vertices in the graph

• Find the shortest route between the two odd vertices

• Add repeats of the edges in this route to the graph

• Any Eulerian circuit using including these edges solves the problem

• The length of the shortest route is the sum of

  • the weights of the edges in the graph

  • and the weights of the repeated edges

If there are two pairs of odd vertices in the graph

• Suppose the odd vertices are A, B, C and D

• Find the shortest route between each pair of these vertices

• Identify which combination has the smallest total weight

  • AB and CD

  • AC and BD

  • AD and BC

• Add repeats of the edges in the routes in this combination to the graph

• Any Eulerian circuit using including these edges solves the problem

• The length of the shortest route is the sum of

  • the weights of the edges in the graph

  • and the weights of the repeated edges

What if I can start and end on different vertices?

• There is a variation of the problem which allows the postman to start and end on different vertices

  • The solution is no different if all the vertices are even

If there is one pair of odd vertices in the graph

• Start on one odd vertex and end on the other

• The length of the route is equal to the weight of the graph

If there are two pairs of odd vertices in the graph

• Suppose the odd vertices are A, B, C and D

• Find the shortest route between each pair of these vertices

  • Choose the pair that has the smallest route and repeat those edges on the graph

• Start and end on the other two odd vertices

• The length of the route is equal to the weight of the graph plus the length of the repeated route