Input description: A graph G=(V,E).
Problem description: Find the shortest tour of G visiting each edge at least once.
Discussion: Suppose you are given the map of a city and charged with designing the routes for garbage trucks, snow plows, or postmen. In all of these applications, every road in the city must be completely traversed at least once in order to ensure that all deliveries or pickups are made. For efficiency, you seek to minimize total drive time, or equivalently, the total distance or number of edges traversed.
Such applications are variants of the Eulerian cycle problem, best characterized by the children's puzzle that asks them to draw a given figure completely without lifting their pencil off the paper and without repeating any edges. We seek a path or cycle through a graph that visits each edge exactly once.
There are well-known conditions for determining whether a graph contains an Eulerian cycle, or path:
Given this characterization of Eulerian graphs, it is easy to test in linear time whether such a cycle exists: test whether the graph is connected using DFS or BFS, and then count the number of odd-degree vertices. Actually constructing such a cycle also takes linear time. Use DFS to find a cycle in the graph. Delete this cycle and repeat until the entire set of edges has been partitioned into a set of edge-disjoint cycles. Since deleting a cycle reduces each vertex degree by an even number, the remaining graph will continue to satisfy the same Eulerian degree-bound conditions. For any connected graph, these cycles will have common vertices, and so by splicing these cycles in a ``figure eight'' at a shared vertex, we can construct a single circuit containing all of the edges.
An Eulerian cycle, if one exists, solves the motivating snowplow problem, since any tour that visits each edge only once must have minimum length. However, it is unlikely that any real road network would happen to satisfy the degree conditions that make it Eulerian. We need to solve the more general Chinese postman problem, which minimizes the length of a cycle that traverses every edge at least once. In fact, it can be shown that this minimum cycle never visits any edge more than twice, so good tours exist for any road network.
The optimal postman tour can be constructed by adding the appropriate edges to the graph G so as to make it Eulerian. Specifically, we find the shortest path between each pair of odd-degree vertices in G. Adding a path between two odd-degree vertices in G turns both of them to even-degree, thus moving us closer to an Eulerian graph. Finding the best set of shortest paths to add to G reduces to identifying a minimum-weight perfect matching in a graph on the odd-degree vertices, where the weight of edge (i,j) is the length of the shortest path from i to j. For directed graphs, this can be solved using bipartite matching, where the vertices are partitioned depending on whether they have more ingoing or outgoing edges. Once the graph is Eulerian, the actual cycle can be extracted in linear time using the procedure described above.
Implementations: Unfortunately, we have not able to identify a suitable
Chinese postman implementation.
However, it should not be difficult for you to roll your
own by using a matching code from Section 
and all-pairs shortest path from Section .
Matching is by far the hardest part of the algorithm.
Combinatorica [Ski90] provides Mathematica implementations
of Eulerian cycles and de Bruijn sequences.
See Section .
Nijenhuis and Wilf [NW78] provide an efficient Fortran
routine to enumerate all Eulerian cycles of a graph by backtracking.
See Section .
Notes: The history of graph theory began in 1736, when Euler [Eul36] first solved the seven bridges of Königsberg problem. Königsberg (now Kaliningrad) is a city on the banks of the Pregel river. In Euler's day there were seven bridges linking the banks and two islands, which can be modeled as a multigraph with seven edges and four vertices. Euler sought a way to walk over each of the bridges exactly once and return home, i.e. an Eulerian cycle. Since all four of the vertices had odd degree, Euler proved that such a tour is impossible. The bridges were destroyed in World War II. See [BLW76] for a translation of Euler's original paper and a history of the problem.
Expositions on linear algorithms for constructing Eulerian cycles [Ebe88] include [Eve79a, Man89]. Fleury's algorithm [Luc91] is a direct and elegant approach to constructing Eulerian cycles. Start walking from any vertex, and erase any edge that has been traversed. The only criterion in picking the next edge is that we avoid using a bridge (edges whose deletion) unless there is no other alternative. No Eulerian graph contains a bridge, but what remains at some point on the walk ceases to be biconnected.
The Euler's tour technique is an important paradigm in parallel graph algorithms. See [Man89] for an exposition. Efficient algorithms exist to count the number of Eulerian cycles in a graph [HP73].
The problem of finding the shortest tour traversing all edges in a graph was introduced by Kwan [Kwa62], hence the name Chinese postman. The bipartite matching algorithm for solving Chinese postman is due to Edmonds and Johnson [EJ73]. This algorithm works for both directed and undirected graphs, although the problem is NP-complete for mixed graphs [Pap76a]. Mixed graphs contain both directed and undirected edges. Expositions of the Chinese postman algorithm include [Law76].
A de Bruijn sequence S of span n on an alphabet 
of size 
is
a circular string of length 
containing all strings of length
n as substrings of S, each exactly once.
For example, for n=3 and 
, the circular string
00011101 contains the following substrings in order: 000, 001, 011, 111,
110, 101, 010, 100.
De Bruijn sequences can be thought of as ``safe cracker'' sequences, describing
the shortest sequence of dial turns with positions
sufficient to try out all combinations of length n.
De Bruijn sequences can be constructed by building a graph whose vertices
are all 
strings of length n-1, where there is an edge
(u,v) iff 
and 
.
Any Eulerian cycle on this graph describes a de Bruijn sequence.
For expositions on de Bruijn sequences and their construction,
see [Eve79a, Ski90].
Related Problems: Matching (see page ),
Hamiltonian cycle (see page ).
