6.4.2 Chinese Postman's Problem on an Undirected Graph

Assume 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 j0 N and draw a circuit through G (thus eventually returning to j0). Let this circuit be denoted C0. If C0 happens to be an Euler tour, this is fine; we stop. If Co is not an Euler tour, then if we remove from G all edges used by circuit C0, there must be someedges left over (not traversed by C0). Moreover, at least two of these edges must be incident on some node jl through which circuit C0 has passed. This must be so since, by assumption, G is, first, connected and, second, all its nodes are of even degree (and C0 has only used up aneven number of edges which are incident on j1). Thus, it is possible to draw another circuit C1. originating and terminating at j1, which uses only edges of G', the graph left after we eliminate the edges of C0 from G. If all edges in G' are used up by C1 , then we are finished: the Euler tour is the circuit that results fromusing the initial portion of C0 to go from j0 to j1 , then C1 to return back to j1 , and finally the second portion of C0 to go from j1to j0 . If, however, after eliminating the edges on C0 and C1 from G. there are still some edges left uncovered, then at least two of these edges mustbe incident on a node j2 which is either on C0 or on C1 (or both if j2 = j1). Then, it should be possible to find a tour C2, originating and terminating at j2 and using only edges on G'', where G'' is the graph that results when the edges covered by C0 and C1 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 C0, C1, C2, . . ., Ck. The tour is constructed in the manner explained above for C0 and C1.

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.

Exercise 6.3 Prove the part of Euler,s theorem which Cairns that an Euler path can be drawn on graphs with exactly two nodes of odd degree.

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.

12In 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).