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 and/or problems:
“Science is the language of the temporal world; love is that of the spiritual world. Man, indeed, describes more than he explains; while the angelic spirit sees and understands. Science saddens man; love enraptures the angel; science is still seeking, love has found. Man judges of nature in relation to itself; the angelic spirit judges of it in relation to heaven. In short to the spirits everything speaks.”
—Honoré De Balzac (1799–1850)
“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)