Solution
If a graph has an Eulerian circuit (or an Eulerian path), then an Eulerian circuit (or path) visits every edge, and so the solution is to choose any Eulerian circuit (or path).
If the graph is not Eulerian, it must contain vertices of odd degree. By the handshaking lemma, there must be an even number of these vertices. To solve the postman problem we first find a smallest T-join. We make the graph Eulerian by doubling of the T-join. The solution to the postman problem in the original graph is obtained by finding an Eulerian circuit for the new graph.
Read more about this topic: Route Inspection Problem
Famous quotes containing the word solution:
“What is history? Its beginning is that of the centuries of systematic work devoted to the solution of the enigma of death, so that death itself may eventually be overcome. That is why people write symphonies, and why they discover mathematical infinity and electromagnetic waves.”
—Boris Pasternak (1890–1960)
“Who shall forbid a wise skepticism, seeing that there is no practical question on which any thing more than an approximate solution can be had? Is not marriage an open question, when it is alleged, from the beginning of the world, that such as are in the institution wish to get out, and such as are out wish to get in?”
—Ralph Waldo Emerson (1803–1882)
“There’s one solution that ends all life’s problems.”
—Chinese proverb.