| Line 8: | Line 8: | ||
In the case where the graph has some odd edges, the solution is more complicated. First, identify all nodes with odd degree. Next, pair up the odd nodes such that the sum of the weights of the shortest paths between pairs is a minimum. Then, take all the edges from the paths in the previous step, and duplicate them. This ensures that all nodes now have even degree, while adding the minimum possible weight to the graph. Finally, the solution is the Euler circuit of the modified graph, and the cost is the sum of all edge weights in the original graph plus the sum of the weights of the duplicated edges. | In the case where the graph has some odd edges, the solution is more complicated. First, identify all nodes with odd degree. Next, pair up the odd nodes such that the sum of the weights of the shortest paths between pairs is a minimum. Then, take all the edges from the paths in the previous step, and duplicate them. This ensures that all nodes now have even degree, while adding the minimum possible weight to the graph. Finally, the solution is the Euler circuit of the modified graph, and the cost is the sum of all edge weights in the original graph plus the sum of the weights of the duplicated edges. | ||
| + | |||
| + | (TODO Analysis) | ||
=== History === | === History === | ||
Revision as of 16:16, 16 April 2016
Contents
Chinese postman problem
Introduction
(Sargun)
The Chinese postman problem, also known as the route inspection problem, is to find a circuit in a connected, undirected graph that visits each edge at least once. Additionally, a correct solution minimizes the total cost of the circuit. If all vertices of the graph have even degree, then the optimal solution is the Euler circuit of the graph. In this case, the cost of the solution is the sum of all edge weights in the graph.
In the case where the graph has some odd edges, the solution is more complicated. First, identify all nodes with odd degree. Next, pair up the odd nodes such that the sum of the weights of the shortest paths between pairs is a minimum. Then, take all the edges from the paths in the previous step, and duplicate them. This ensures that all nodes now have even degree, while adding the minimum possible weight to the graph. Finally, the solution is the Euler circuit of the modified graph, and the cost is the sum of all edge weights in the original graph plus the sum of the weights of the duplicated edges.
(TODO Analysis)
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 mathematics researchers focused on problems like transportation and production planning. And Shandong province, as a center of early Chinese mathematics 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 neighborhood. He needs to walk through all the streets in the neighborhood 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.
