Chinese postman problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 neighborhood. The mailman is unwilling to walk far, so he wants to find the shortest route through the neighborhood, 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 traveled has an Eulerian Circuit, 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]

Other websites[change | edit source]

References[change | edit source]