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:
“The route through childhood is shaped by many forces, and it differs for each of us. Our biological inheritance, the temperament with which we are born, the care we receive, our family relationships, the place where we grow up, the schools we attend, the culture in which we participate, and the historical period in which we live—all these affect the paths we take through childhood and condition the remainder of our lives.”
—Robert H. Wozniak (20th century)
“Thus the orb he roamed
With narrow search, and with inspection deep
Considered every creature, which of all
Most opportune might serve his wiles, and found
The serpent subtlest beast of all the field.”
—John Milton (1608–1674)
“To make a good salad is to be a brilliant diplomatist—the problem is entirely the same in both cases. To know exactly how much oil one must put with one’s vinegar.”
—Oscar Wilde (1854–1900)