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:
“In the mountains the shortest route is from peak to peak, but for that you must have long legs. Aphorisms should be peaks: and those to whom they are spoken should be big and tall of stature.”
—Friedrich Nietzsche (1844–1900)
“Hermann Goering, Joachim von Ribbentrop, Albert Speer, Walther Frank, Julius Streicher and Robert Ley did pass under my inspection and interrogation in 1945 but they only proved that National Socialism was a gangster interlude at a rather low order of mental capacity and with a surprisingly high incidence of alcoholism.”
—John Kenneth Galbraith (b. 1908)
“A serious problem in America is the gap between academe and the mass media, which is our culture. Professors of humanities, with all their leftist fantasies, have little direct knowledge of American life and no impact whatever on public policy.”
—Camille Paglia (b. 1947)