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)
“Any solution to a problem changes the problem.”
—R.W. (Richard William)
“Let us begin to understand the argument.
There is a solution to everything: Science.”
—Allen Tate (1899–1979)