Route inspection problem
From Wikipedia, the free encyclopedia
In graph theory, a branch of mathematics, the Chinese postman problem or route inspection problem is to find a shortest closed path (circuit) that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit, that circuit is an optimal solution.
Alan Goldman of NIST first coined the name 'Chinese Postman Problem' for this problem, as it was originally studied by the Chinese mathematician Mei Ko Kuan in 1962.
[edit] Eulerian paths and circuits
In order for a graph to have a closed Eulerian path, it will certainly have to be connected.
So suppose we have a connected graph G = (V, E), the following statements are equivalent:
- All vertices in G have even valence (degree).
- G consists of the edges from a disjoint union of some cycles, and the vertices from these cycles.
- G has an Eulerian path.
- → 2. can be shown by induction on the number of cycles.
- → 3. can also be shown by induction on the number of cycles, and
- → 1. should be immediate.
A semi-Eulerian path (a path 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 non-even valence.
[edit] Solution
If a graph is Eulerian, then an Eulerian path visits every edge, and so the solution is to choose any Eulerian path.
If the graph is not Eulerian, it must contain vertices of odd degree. By a result in graph theory, there must be an even number of these types of vertices. Note that we must revisit edges that come out of these vertices for the solution. We make the graph Eulerian by doubling the paths that connect these vertices in pairs. We choose the pairs such that the total distance covered of all paths that connect these vertices are as small as possible. Now the solution is an Eulerian path for this new graph.
