(Format headings) |
|||
| Line 1: | Line 1: | ||
| − | == Chinese | + | == Chinese postman problem == |
=== Introduction === | === Introduction === | ||
(Sargun) | (Sargun) | ||
| + | |||
| + | The Chinese postman problem, also known as the route inspection problem, is to find the smallest circuit in an undirected graph that visits each edge at least once. If the graph is not a connected graph, then no solution exists. If all vertices of the graph have even degree, then the graph has an Eulerian circuit and that circuit is the optimal solution. In the case where the graph has some odd edges, the solution is more complicated. | ||
| + | |||
| + | (TODO T-Joins, solve odd case) | ||
=== History === | === History === | ||
| Line 9: | Line 13: | ||
(Hao Xu) | (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 | + | 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 | + | 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 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." | ||
| Line 19: | Line 23: | ||
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." | 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 | + | === Real-world applications === |
(Zexuan Zhou) | (Zexuan Zhou) | ||
Revision as of 20:28, 15 April 2016
Contents
Chinese postman problem
Introduction
(Sargun)
The Chinese postman problem, also known as the route inspection problem, is to find the smallest circuit in an undirected graph that visits each edge at least once. If the graph is not a connected graph, then no solution exists. If all vertices of the graph have even degree, then the graph has an Eulerian circuit and that circuit is the optimal solution. In the case where the graph has some odd edges, the solution is more complicated.
(TODO T-Joins, solve odd case)
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.
