Chinese postman problem
in graph theory, the problem to find a shortest closed path or circuit that visits every edge of an undirected graph
The Chinese postman problem is a mathematical problem of graph theory. It is also known as route inspection problem. Suppose there is a mailman who needs to deliver mail to a certain neighbourhood. The mailman is unwilling to walk far, so he wants to find the shortest route through the neighbourhood, that meets the following criteria:
- It is a closed circuit (it ends at the same point it starts).
- He needs to go through every street at least once.
If the graph travelled has an Eulerian path, this circuit is the ideal solution.
Alan Goldman of the U.S. National Bureau of Standards first coined the name 'Chinese Postman Problem' for this problem, as it was originally studied by the Chinese mathematician Mei-Ku Kuan in 1962.[1]
