Chinese postman problem

[1] It can be solved in polynomial time,[2] unlike the Travelling Salesman Problem which is NP-hard.

[4] The original name "Chinese postman problem" was coined in his honor; different sources credit the coinage either to Alan J. Goldman or Jack Edmonds, both of whom were at the U.S. National Bureau of Standards at the time.

[5][6] A generalization takes as input any set T of evenly many vertices, and must produce as output a minimum-weight edge set in the graph whose odd-degree vertices are precisely those of T. This output is called a T-join.

The undirected route inspection problem can be solved in polynomial time by an algorithm based on the concept of a T-join.

The edges of this matching represent paths in the original graph, whose union forms the desired T-join.

Doubling the edges of a T-join causes the given graph to become an Eulerian multigraph (a connected graph in which every vertex has even degree), from which it follows that it has an Euler tour, a tour that visits each edge of the multigraph exactly once.

[2][8] Various combinatorial problems have been reduced to the Chinese Postman Problem, including finding a maximum cut in a planar graph and a minimum-mean length circuit in an undirected graph.

A worked example of an undirected Chinese postman problem:
  1. Each street must be traversed at least once, starting and ending at the post office at A.
  2. Four vertices with odd degree (orange) are found on its equivalent graph.
  3. The pairing with the lowest total length is found.
  4. After corresponding edges are added (red), the length of the Eulerian circuit is found.