6.6 Chinese postman problem on a directed network To solve the CPP on a directed network [BELT 74], we begin by quoting the version of Euler's theorem that applies to directed networks:

A connected directed network possesses an Euler tour if and only if the indegree and the outdegree of every one of its nodes are equal.

The proof of this theorem is completely analogous to the proof of Euler's theorem for undirected networks (you may wish to retrace its steps).

To solve the CPP on any directed graph, we first define

Pi = "polarity" of i = (indegree of i) - (outdegree of i)

A node i for which Pt > O (Pi < o) is called a "supply" ("demand") node. we indicate the sets of supply and demand nodes as s and d, respectively.

The following algorithm solves the CPP on directed graphs (the algorithm is stated informally):
STEP 1: Identify all supply and demand nodes and compute the polarities of each and the minimum distanced (i,j) from all nodes i S to all nodes j D.
STEP 2: Solve a transportation problem (TP) to find the optimum "matchings" of supply with demand nodes. This TP is:

STEP 3: For each xij > O in the solution to the TP, add to G, xij replications of the shortest path from i S to j D. The resulting network G' has Pi = O for all nodes.
STEP 4: Find an Euler tour on G'. This tour is a solution to the CPP on G.
b. Write a paragraph explaining what the algorithm above does and why. Can any links be traversed more than twice in the CPP solution?
c. Apply the algorithm above to solve the CPP on the directed network of Figure P6.6. Describe a minimum-length tour that begins and concludes at node b.

Hint: The optimal solution requires coverage of 28 units of distance over and above the length of the network.

d. Suppose now that G is a mixed graph (i.e., it has both directed and undirected links). It might be thought that in order to solve the CPP on such a network one could (1) substitute all undirected links (i, j) with two directed links (i, j) and (j, i) of equal length (and of opposite directivities); and (2) apply the algorithm (for the CPP on directed graphs) described above to the resulting directed network. What is wrong with this approach? As we noted earlier in the chapter, no efficient algorithm is available for the CPP on mixed graphs and the problem has in fact been shown to be NP-complete.