Route inspection problem
|
|
Route inspection problem, Chinese postman problem:
The Chinese postman problem is to find a shortest closed path (circuit) that goes through all edges of a (connected) undirected graph. When the graph has an eulerian circuit, that circuit is an optimal solution.
This problem is sometimes called the Chinese Postman Problem because it was first studied by the Chinese mathematician Mei Ko Kuan.
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 consist of the edges from a disjoint union of some cycles, and the vertices from these cycles.
- G has a 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 use all edges of G and all vertices of G just once) exists if and only if G is connected and exactly two vertices have non-even valence.
External links
- Chinese Postman Problem (http://mathworld.wolfram.com/ChinesePostmanProblem.html)de:Briefträgerproblem