Chapter 11, Problem 1RE

Solve the Chinese Postman Problem for the two graphs.

To determine

The Chinese Postman Problem for the two graphs.

Explanation of Solution

In order solve the Chinese postman problem in a connected and possibly weighted graph, we have found at least one walk that covers every edge at least once.

In this question we have to solve the Chinese Postman for following graphs.

For the left un-weighted we need to repeat the two edges between odd-subtended vertices A, B, C, D as shown in the top figure below.

For a weighted graph we have to add four edges between odd-thin ends to get a path.

Following calculations are needed to calculate the shortest paths in case of weighted graph.

Weighted Case

Partition into pairs	Sum of lengths of shortest paths
$\begin{array}{l}\left\{A,B\right\},\left\{C,D\right\}\\ \left\{A,C\right\},\left\{B,D\right\}\\ \left\{A,D\right\},\left\{B,C\right\}\end{array}$	$\begin{array}{l}3+4=7\\ 4+3=7\\ 4+1=5\end{array}$