A problem asking for the shortest tour of a graph which visits each edge at least once (Kwan 1962; Skiena 1990, p. 194). For an Eulerian graph, an Eulerian cycle is the optimal solution. In a tree, however, the path crosses each edge twice.
Chinese Postman Problem
See also
Eulerian Cycle, Traveling Salesman ProblemExplore with Wolfram|Alpha
References
Edmonds, J. and Johnson, E. L. "Matching, Euler Tours, and the Chinese Postman." Math. Programm. 5, 88-124, 1973.Kwan, M. K. "Graphic Programming Using Odd or Even Points." Chinese Math. 1, 273-277, 1962.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Referenced on Wolfram|Alpha
Chinese Postman ProblemCite this as:
Weisstein, Eric W. "Chinese Postman Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ChinesePostmanProblem.html