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:
“We shall never resolve the enigma of the relation between the negative foundations of greatness and that greatness itself.”
—Jean Baudrillard (b. 1929)
“You see, I am alive, I am alive
I stand in good relation to the earth
I stand in good relation to the gods
I stand in good relation to all that is beautiful
I stand in good relation to the daughter of Tsen-tainte
You see, I am alive, I am alive”
—N. Scott Momaday (b. 1934)
“She has problems with separation; he has trouble with unity—problems that make themselves felt in our relationships with our children just as they do in our relations with each other. She pulls for connection; he pushes for separateness. She tends to feel shut out; he tends to feel overwhelmed and intruded upon. It’s one of the reasons why she turns so eagerly to children—especially when they’re very young.”
—Lillian Breslow Rubin (20th century)