Relation Between Problems
There is a simple relation between the problems of finding a Hamiltonian path and a Hamiltonian cycle. In one direction, the Hamiltonian path problem for graph G is equivalent to the Hamiltonian cycle problem in a graph H obtained from G by adding a new vertex and connecting it to all vertices of G. Thus, finding a Hamiltonian path cannot be significantly slower (in the worst case, as a function of the number of vertices) than finding a Hamiltonian cycle.
In the other direction, a graph G has a Hamiltonian cycle using edge uv if and only if the graph H obtained from G by replacing the edge by a pair of vertices of degree 1, one connected to u and one connected to v, has a Hamiltonian path. Therefore, by trying this replacement for all edges incident to some chosen vertex of G, the Hamiltonian cycle problem can be solved by at most n Hamiltonian path computations, where n is the number of vertices in the graph.
The Hamiltonian cycle problem is also a special case of the travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).
Read more about this topic: Hamiltonian Path Problem
Famous quotes containing the words relation between, relation and/or problems:
“There is a relation between the hours of our life and the centuries of time. As the air I breathe is drawn from the great repositories of nature, as the light on my book is yielded by a star a hundred millions of miles distant, as the poise of my body depends on the equilibrium of centrifugal and centripetal forces, so the hours should be instructed by the ages and the ages explained by the hours.”
—Ralph Waldo Emerson (1803–1882)
“Unaware of the absurdity of it, we introduce our own petty household rules into the economy of the universe for which the life of generations, peoples, of entire planets, has no importance in relation to the general development.”
—Alexander Herzen (1812–1870)
“I believe that if we are to survive as a planet, we must teach this next generation to handle their own conflicts assertively and nonviolently. If in their early years our children learn to listen to all sides of the story, use their heads and then their mouths, and come up with a plan and share, then, when they become our leaders, and some of them will, they will have the tools to handle global problems and conflict.”
—Barbara Coloroso (20th century)