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:
“I can’t quite define my aversion to asking questions of strangers. From snatches of family battles which I have heard drifting up from railway stations and street corners, I gather that there are a great many men who share my dislike for it, as well as an equal number of women who ... believe it to be the solution to most of this world’s problems.”
—Robert Benchley (1889–1945)
“Coming out, all the way out, is offered more and more as the political solution to our oppression. The argument goes that, if people could see just how many of us there are, some in very important places, the negative stereotype would vanish overnight. ...It is far more realistic to suppose that, if the tenth of the population that is gay became visible tomorrow, the panic of the majority of people would inspire repressive legislation of a sort that would shock even the pessimists among us.”
—Jane Rule (b. 1931)
“The truth of the thoughts that are here set forth seems to me unassailable and definitive. I therefore believe myself to have found, on all essential points, the final solution of the problems. And if I am not mistaken in this belief, then the second thing in which the value of this work consists is that it shows how little is achieved when these problems are solved.”
—Ludwig Wittgenstein (1889–1951)