Chinese postman problem

From Simple English Wikipedia, the free encyclopedia

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. That mailman is lazy, so he wants to find a route through the neighborhood, that meets the following criteria

  • It is a closed circuit, that is it ends at the points it starts.
  • He needs to go through each street only once.
  • Every street of the neighborhood is included in the path.

If the graph travelled has an Eulerian Circuit, this circuit is the ideal solution

[edit] External links


In other languages