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.¹²

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

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.

¹²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).