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.
In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph at least once. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate (or the subset of edges with the minimum possible total weight) so that the resulting multigraph does have an Eulerian circuit.[1] It can be solved in polynomial time,[2] unlike the Travelling Salesman Problem which is NP-hard.[3] It is different from the Travelling Salesman Problem in that the travelling salesman cannot repeat visited nodes.
The problem was originally studied by the Chinese mathematician Kwan Mei-Ko in 1960, whose Chinese paper was translated into English in 1962.[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 is to choose any set T of evenly many vertices that are to be joined by an edge set in the graph whose odd-degree vertices are precisely those of T. Such a set is called a T-join. This problem, the T-join problem, is also solvable in polynomial time by the same approach that solves the postman problem.
^Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 640–642, ISBN 9781420099829
^Cite error: The named reference EdmondsJohnson was invoked but never defined (see the help page).
^"The Travelling Salesman Problem" (PDF).
^Kwan, Mei-ko (1960), "Graphic programming using odd or even points", Acta Mathematica Sinica (in Chinese), 10: 263–266, MR 0162630. Translated in Chinese Mathematics1: 273–277, 1962.
^Pieterse, Vreda; Black, Paul E., eds. (September 2, 2014), "Chinese postman problem", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, retrieved 2016-04-26
^Grötschel, Martin; Yuan, Ya-xiang (2012), "Euler, Mei-Ko Kwan, Königsberg, and a Chinese postman" (PDF), Optimization stories: 21st International Symposium on Mathematical Programming, Berlin, August 19–24, 2012, Documenta Mathematica, Extra: 43–50, MR 2991468.
and 23 Related for: Chinese postman problem information
and computer science, Guan's route problem, the Chinesepostmanproblem, postman tour or route inspection problem is to find a shortest closed path or...
The mixed Chinesepostmanproblem (MCPP or MCP) is the search for the shortest traversal of a graph with a set of vertices V, a set of undirected edges...
Chinese PostmanProblem (CPP), the Windy PostmanProblem (WPP), the Rural PostmanProblem (RPP), the k-Chinesepostmanproblem (KCPP), the mixed Chinese postman...
art. Canadian traveller problem Exact algorithm Route inspection problem (also known as "Chinesepostmanproblem") Set TSP problem Seven Bridges of Königsberg...
problem Minimum spanning tree Route inspection problem (also called the "Chinesepostmanproblem") Seven bridges of Königsberg Shortest path problem Steiner...
with complicating constraints and decision sets. Chinesepostmanproblem Vehicle rescheduling problem Arc routing List of graph theory topics Dantzig,...
cost of plowing downhill compared to plowing uphill. The Mixed ChinesePostmanProblem is applicable to snow routes where directed edges represent one-way...
parallelogrammatique projection, an equirectangular map projection Chinesepostmanproblem, a mathematical problem in graph theory meta-Chlorophenylpiperazine, a chemical...
simultaneous routes to reach the destinations. The Route inspection or "ChinesePostman" problem asks for the optimal (least distance/cost) path that traverses...
vision: 267–276 Arc routing problem, including ChinesePostmanproblem Talent Scheduling, scenes shooting arrangement problem Branch-and-bound may also be a base...
Edmonds, who gave the problem its alternative name, the "Chinesepostmanproblem", in honor of Guan, and proved that this problem can be solved optimally...
Postman Pat is a British stop-motion animated television series first produced by Woodland Animations. The series follows the adventures of Pat Clifton...
herbicide Mississippi Center for Public Policy Mixed Chinesepostmanproblem – a search problem in mathematics The Modern Corporation and Private Property...
closed curve L that covers all the arcs of the graph. (L is called a Chinesepostman tour). Then, traverse L with probability 1/2 for each direction. This...
He has won the Hugo, Locus, Campbell and Nebula Awards. His novel The Postman was adapted into a 1997 feature film starring Kevin Costner. Brin was born...
The cinema of China is the filmmaking and film industry of the Chinese mainland under the People's Republic of China, one of three distinct historical...
Gordon; Leo Postman (1951). Psychology of Rumor. Russell and Russell. p. 75. Bordia, Prashant; Nicolas DiFonzo (March 2004). "Problem Solving in Social...
2305/IUCN.UK.2021-2.RLTS.T61611928A61611931.en. Retrieved 25 January 2024. Postman, Joseph (2009). "Cydonia oblonga: The unappreciated quince" (PDF). Arnoldia...
Wonderland), a gardener Pat (Saturday Night Live), an androgynous character Postman Pat, a British children's TV character Pat, from the Czech series Pat &...
enhanced by her critically acclaimed performance in the film noir The Postman Always Rings Twice (1946), a role which established her as a serious dramatic...
word "nobel" (Chinese: 諾貝爾; Jyutping: nok6 bui3 ji5), one might first think about the Nobel Prize rather than Chernobyl, in Chinese: (Chinese: 諾貝爾獎; Jyutping:...
Global Information