Route inspection problem
In graph theory, a branch of mathematics, the Chinese postman problem (CPP), postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the optimization problem is to find the fewest number of edges to add to the graph so that the resulting multigraph does have an Eulerian circuit.
Alan Goldman of the U.S. National Bureau of Standards first coined the name 'Chinese Postman Problem' for this problem, as it was originally studied by the Chinese mathematician Kwan Mei-Ko in 1962.
Eulerian paths and circuits
Suppose we have a connected graph G = (V, E), The following statements are equivalent:
- All vertices in G have even degree.
- G consists of the edges from a disjoint union of some cycles, and the vertices from these cycles.
- G has an Eulerian circuit.
- 1 → 2 can be shown by induction on the number of cycles.
- 2 → 3 can also be shown by induction on the number of cycles, and
- 3 → 1 should be immediate.
An Eulerian path (a walk which is not closed but uses all edges of G just once) exists if and only if G is connected and exactly two vertices have odd valence (degree).
Let T be a subset of the vertex set of a graph. An edge set is called a T-join if in the induced subgraph of this edge set, the collection of all the odd-degree vertices is T. (In a connected graph, a T-join exists if and only if |T| is even.) The T-join problem is to find a smallest T-join. When T is the set of all odd-degree vertices, a smallest T-join leads to a solution of the postman problem. For any T, a smallest T-join necessarily consists of |T| paths, no two having an edge in common, that join the vertices of T in pairs. The paths will be such that the total length of all of them is as small as possible. A minimum T-join can be obtained using a weighted matching algorithm that uses O(n3) computational steps.
If a graph has an Eulerian circuit (or an Eulerian path), then an Eulerian circuit (or path) visits every edge, and so the solution is to choose any Eulerian circuit (or path).
If the graph is not Eulerian, it must contain vertices of odd degree. By the handshaking lemma, there must be an even number of these vertices. To solve the postman problem we first find a smallest T-join. We make the graph Eulerian by doubling of the T-join. The solution to the postman problem in the original graph is obtained by finding an Eulerian circuit for the new graph.
Various combinatorial problems are reduced to the Chinese Postman Problem, including finding a maximum cut in a planar graph and a minimum-mean length circuit in an undirected graph.
- Minimize the Chinese postman problem for mixed graphs: for this problem, some of the edges may be directed and can therefore only be visited from one direction. When the problem calls for a minimal traversal of a digraph (or multidigraph) it is known as the "New York Street Sweeper problem."
- Minimize the k-Chinese postman problem: find k cycles all starting at a designated location such that each edge is traversed by at least one cycle. The goal is to minimize the cost of the most expensive cycle.
- Eulerian path - Path that visits all edges in the graph exactly once. It may or may not exist.
- Travelling salesman problem
- Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 640–642, ISBN 9781420099829
- ""Chinese Postman Problem"". - NIST
- Lawler, E.L. (1976), Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston
- Edmonds, J.; Johnson, E.L. (1973), Matching Euler tours and the Chinese postman problem, Mathematical Programming 5: 88–124
- A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002).
- Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH NADA, Stockholm. Retrieved 2008-10-22.
- Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 642–645, ISBN 9781420099829