In graph theory, a branch of mathematics, the Chinese postman problem (CPP), postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal 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.
Read more about Route Inspection Problem: Eulerian Paths and Circuits, T-joins, Solution, Variants
Famous quotes containing the words route, inspection and/or problem:
“A route differs from a road not only because it is solely intended for vehicles, but also because it is merely a line that connects one point with another. A route has no meaning in itself; its meaning derives entirely from the two points that it connects. A road is a tribute to space. Every stretch of road has meaning in itself and invites us to stop. A route is the triumphant devaluation of space, which thanks to it has been reduced to a mere obstacle to human movement and a waste of time.”
—Milan Kundera (b. 1929)
“We had an inspection today of the brigade. The Twenty-third was pronounced the crack regiment in appearance, ... [but] I could see only six to ten in a company of the old men. They all smiled as I rode by. But as I passed away I couldn’t help dropping a few natural tears. I felt as I did when I saw them mustered in at Camp Chase.”
—Rutherford Birchard Hayes (1822–1893)
“The problem of the twentieth century is the problem of the color-line—the relation of the darker to the lighter races of men in Asia and Africa, in America and the islands of the sea. It was a phase of this problem that caused the Civil War.”
—W.E.B. (William Edward Burghardt)