Kwan Mei-Ko developed the Chinese Postman Problem: A postman has to leave from a depot, travel along a set number of roads to deliver the mail, then return to the depot. How should he do this so that he travels the minimum distance?

Essentially the problem is about travelling along every edge of a weighted graph and then returning to the starting vertex.

If all of the vertices have even degree, the graph is Eulerian and any Eulerian circuit will be a solution to the problem.

If the graph is not Eulerian, some of the edges must be walked twice to solve the problem. The task is to minimise the total weight of the edges we walk twice. Because semi-Eulerian graphs have exactly two vertices with odd degree, we need to walk twice along the edges forming the shortest path between the odd vertices. If the graph is relatively small, we can do this by inspection.

If there are more than two vertices of odd degree, we must consider each possible pairing of the vertices.

Worked Example 1

Solve the Chinese Postman Problem for the following weighted graph:

Worked Example 2

Solve the Chinese Postman Problem for the following weighted graph:

Exercise

Answers