Contents
Chinese Postman Problem
Introduction
(Sargun)
History
(Hao Xu)
During the Great Leap Forward movement period in the Chinese history (1958-1960), president Mao of China encouraged scientists to solve real-world problems in order to accelerate the transformation of economy mode of China. At that time, many mathematic researchers focused on problems like transportation and production planning. And Shandong province, as a center of early Chinese mathematic researches, is where Chinese Postman Problem was created. (Grotschel & Yuan, 2010).
Chinese Postman Problem was discovered by a Chinese mathematician --- Kwan Mei-Ko. The problem described a situation that the Chinese postman would face everyday. The exact problem was defined in Kwan's paper as, "A postman has to deliver letters to a given neighbourhood. He needs to walk through all the streets in the neighbourhood and back to the post-office. How can he design his route so that he walks the shortest distance?"
Then he converted this problem to a more generic one by counting the number of edges linked to a node as, "Given a connected graph where 2n of the nodes are odd and all other nodes are even. Suppose we need to add some edges to the graph with the following property: the number of edges added to any odd node is odd and that added to any even node is even. We need to minimize the total length of the added edges."
Then he solved this problem by his theorem, which is also in his paper, "For a set of added edges it is necessary and sufficient to be an optimal solution for the above problem if the following two conditions hold: 1). Between any two nodes, no more than one edge is added, 2). In any cycle of the extended graph, the total length of the added edge is not greater than half of the total length of the cycle."
Real-world Applications
(Zexuan Zhou)
Variations
(Evan)
Examples
(Hao Wu)
References
Kwan, M. K. (1960). Programming method using odd or even pints, Acta Mathematica sinica, 10, 263-266.
Grotschel, M., & Yuan, Y. X. (2010). Euler, Mei-ko Kwan, Konigsberg, and a Chinese postman. Documenta Math., 43-50.
