6.4.4 Solving the Chinese Postman's ProblemWe now return to the Chinese postman,s problem and solve the problem of finding the minimum length, edgecovering tour of a graph G(N, A) with no restrictions placed on G other than that it be connected and undirected. The solution procedure consists of adding, in a judicious manner, artificial edges, parallel to the existing ones, to the original graph G to obtain a new graph G^{1}(N, A^{1}) on which an Euler tour can be drawn. This means that the addition of the artificial edges should be such as to turn all odddegree nodes on G into evendegree nodes on G^{1}. Moreover, this should be accomplished by selecting that combination of artificial edges which results in the minimumlength tour at the end. The addition of an artificial edge in parallel to an existing one in the original network simply means that the existing edge will have to be traversed twice in the final Chinese postman,s tour. An important observation is helpful at this point. Lemma: The number of nodes of odd degree in an undirected graph G is always even.
We now describe the solution approach in general terms: Chinese Postman AlgorithmUndirected Graph (Algorithm 6.5)
A pairwise matching of a subset N' N of nodes of a graph G is a pairing of all the nodes in N' (assuming that the number of nodes in N' is even). A minimumlength pairwise matching of the nodes in An is then a matching such that the total length of the shortest paths between the paired nodes is minimum.
In Algorithm 6.5, we have concentrated exclusively on the shortest paths between pairs of odddegree nodes. That this should be so can be seen as follows. Were a supposedly optimal pairwise matching between odddegree nodes to contain a path, P^{1}, between any given pair of nodes that is not the shortest path, P. between these two nodes, the solution could be improved by simply substituting P for P^{1} in the drawing of the artificial edges, since the length of P is, by definition, smaller than the length of P^{1}. In reviewing Algorithm 6.5, we can see that its only difficulty lies in
Step 2, since Steps 1, 3, and 4 are all very simple. For Step 2, however,
the number of possible pairwise matching combinations increases very quickly
with the number of odddegree nodes. Some thought will show that with m odd
degree nodes in G (remember that m is always even), there are
possible distinct pairwise matching combinations. Thus, for m = 4, there are I · 3 = 3 possible combinations (as we have already seen in our last example), for m = 10,945 combinations, and for m = 20, about 655 million combinations. Fortunately, an efficient, but quite complicated algorithm for minimum length matchings on undirected graphs is now available. This algorithm is based on the theory of matching on graphs that has been developed in recent years primarily by J. Edmonds. The interested reader is referred to [EDMO 73] or to [CHRI 753 for its details. Here we only note that the algorithm is an exact one (i.e., finds the optimum matchings) and efficient computerimplemented versions solve the problem in time proportional to n^{3}, where n is the number of nodes in the graph under consideration. The algorithm not only finds the minimumlength matchings but also identifies the shortest path associated with each pair. It follows that in the worst case Algorithm 6.5 is also O(n^{3}). Manual approach to matching. When Edmonds' minimumlength matching algorithm is used in Step 2 of Algorithm 6.5, an optimum solution to the Chinese postman,s problem is obtained. Experience has shown, however, that whenever the Chinese postman problem is posed in a geographical context (and this of course is the case in urban service systems applications), then excellentin the sense of being very close to the optimummanual solutions can be obtained practically by inspection with the aid of a good map. The map can be used to perform all four steps of Algorithm 6.5, and the only step where one risks deviating from the optimum solution is in finding the minimumlength matching in Step 2. The manual search for an approximately minimumlength matching of odddegree nodes in Step 2 is greatly aided by the following key observation: In a minimumlength matching of the odddegree nodes, no two shortest paths in the matching can have any edges in common. To see this, consider Figure 6.16, assuming that nodes a, b, c, and d are
all of odd degree and that the shortest paths between, say, the pairs of
nodes ac and Kd have edge (p, q) in common. Then it is impossible that the
minimumlength pairwise matching contain the pairs ac and Fd, since it would
then be possible to obtain a better (shorter) matching by coupling
together nodes a and b into one pair and nodes c and d into another. This latter matching will reduce the sum of the shortest path lengths by at least 2 (p, q) units.
Other observations (of a somewhat more complicated nature) have also been made (see [STRI 70]) with regard to finding good approximate solutions to minimumlength matching problems without using a matching algorithm. It has been the authors' experience that, whenever good maps of urban areas are available, it takes only a limited amount of practice with some examples before one develops the ability to find virtually by inspection excellent solutions to matching problems (by taking advantage of the foregoing observations).
