Undirected Chinese Postman

The Undirected Chinese Postman Problem asks for the minimum cost closed walk that visits every edge of an undirected graph at least once. If the graph is Eulerian (every vertex has an even degree) and connected, the Eulerian circuit itself is the optimal walk, and its cost is simply the sum of all edge weights. If there are vertices with odd degrees, we must traverse some edges more than once. We do this by finding a minimum-weight perfect matching among the odd-degree vertices and duplicating the paths between matched pairs.

Experiment

In the interactive module, you can explore various preset graphs using the Graph control. Observe how the number of odd-degree vertices impacts the matching and the total added cost.

1. Select Square tail from the Graph control to see a graph with 2 odd vertices. Note the matched odd pairs and the added traversal cost.
2. Select Star from the Graph control to see a graph with 4 odd vertices. Observe the red dashed curves indicating the duplicate traversals forming the minimum perfect matching.