6.4.2 Chinese Postman's Problem on an Undirected GraphAssume that an undirected graph G(N, A) is given with known edge lengths (i, j) (> O) for all edges (i, j) A. [As usual, (i, j) could also represent cost, travel time, and so on, associated with edge (i, j), dependingon the context of the problem.] Then the CPP can be formally stated as follows: Find a circuit that will traverse every edge of G at least once and for
which the sum
where n(i, j) is the number of times edge (i, j) is traversed. The following definitions are now necessary for our subsequent discussion: Definitions: An Euler tour is a circuit which traverses every edge on a graph exactly once (beginning and terminating at the same node). An Euler path is a path which traverses every edge on a graph exactly once. We then have the following fundamental result: Euler's Theorem: A connected graph G possesses an Euler tour (Euler path) if and only if G contains exactly zero (exactly two) nodes of odd degree.^{12} Figure 6.14 illustrates Euler,s theorem. Figure 6.14a and b have no nodes
of odd degree and must, therefore, possess an Euler tour. Such a tour, for
instance, is the circuit {B. C, D, A, C, A, B} for the graph of Figure 6.14b
(note that the A-C-A portion of the tour can be traversed in either of two
ways). Graphs 6.14c and d have exactly two nodes of odd degree. Thus, they
must possess an Euler path according to the theorem. For instance, {A, B, D, E
C, A, F, C, B, E, F} is an Euler path for graph 6.14d. (By the way, Euler paths are
simple but not always elementary.) However, it is impossible to find an Euler path
that does not begin at A and terminate at F, or begin at F and terminate at A.
Finally, graphs 6.14e and f have four nodes of odd degree, and thus neither
an Euler tour nor an Euler path can be drawn on either. Note that graph 6.14f is
a network model of the Konigsberg problem with the seven bridges.
Proof of Euler's theorem: Assume that G has zero nodes of odd degree. It can then be shown that this is a necessary and a sufficient condition for an Euler tour to exist. It is necessary because any Euler tour drawn on the graph must always enter a node through some edge and leave through another and all edges on the graph must be used exactly once. Thus, an even number of incident edges is required for every node on the graph. Sufficiency, on the other hand, can be shown through the following tour construction argument. We begin at some initial node j_{0} N and draw a circuit through G (thus eventually returning to j_{0}). Let this circuit be denoted C_{0}. If C_{0} happens to be an Euler tour, this is fine; we stop. If C_{o} is not an Euler tour, then if we remove from G all edges used by circuit C_{0}, there must be someedges left over (not traversed by C_{0}). Moreover, at least two of these edges must be incident on some node jl through which circuit C_{0} has passed. This must be so since, by assumption, G is, first, connected and, second, all its nodes are of even degree (and C_{0} has only used up aneven number of edges which are incident on j_{1}). Thus, it is possible to draw another circuit C_{1}. originating and terminating at j_{1}, which uses only edges of G', the graph left after we eliminate the edges of C_{0} from G. If all edges in G' are used up by C_{1} , then we are finished: the Euler tour is the circuit that results fromusing the initial portion of C_{0} to go from j_{0} to j_{1} , then C_{1} to return back to j_{1} , and finally the second portion of C_{0} to go from j_{1}to j_{0} . If, however, after eliminating the edges on C_{0} and C_{1} from G. there are still some edges left uncovered, then at least two of these edges mustbe incident on a node j_{2} which is either on C_{0} or on C_{1} (or both if j_{2} = j_{1}). Then, it should be possible to find a tour C_{2}, originating and terminating at j_{2} and using only edges on G'', where G'' is the graph that results when the edges covered by C_{0} and C_{1} are eliminated from G. This procedure may now be continued until eventually, say after the kth step, there will be no edges left uncovered. At that time, an Euler tour will also have been obtained which will be a combination of circuits C_{0}, C_{1}, C_{2}, . . ., C_{k}. The tour is constructed in the manner explained above for C_{0} and C_{1}. It is interesting to note that the tour-construction approach that we have just outlined in proving sufficiency happens, in fact, to be one of the possible algorithms that can be used in practice to construct Euler tours on graphs.
What are now the implications of Euler's theorem for the Chinese postman's problem ? First, and obviously, if a graph possesses an Euler tour, then this tour is clearly the solution to the Chinese postman's problem. More important, however, as we shall now see, Euler,s theorem provides the guidelines for solving the Chinese postman,s problem, even for graphs on which an Euler tour does not exist. The solution approach basically consists of augmenting these graphs in such a way that all odd-degree nodes are transJormed to even-degree nodes, which in turn means that an Euler tour can be drawn on the augmented graph. Before discussing the details of this solution approach, we shall present an algorithm for drawing Euler tours on graphs where such tours are known to exist. ^{12}In the case of directed graphs, Euler's theorem requires that the indegree and outdegree of each node must be equal to exist (see Problem 6.6). |