Question

Explain why Hamilton's first equi circuit beginning from a given initial sequence rst problem is equivalent to the problem of finding a Hamilton 4.In of five vertices. ices in the desired circuit.

Answer 1

Answer :-

There is a simple relation between the problems of finding a Hamiltonian path and Hamiltonian circuit

• In one direction, the Hamiltonian path problem for graph G is equivalent to the Hamiltonian circuit problem in a graph H obtained from G by adding a new vertex x and connecting x 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 circuit.
• In the other direction, the Hamiltonian circuit problem for a graph G is equivalent to the Hamiltonian path problem in the graph H obtained by copying one vertex v of G, v', that is, letting v' have the same neighbourhood as v, and by adding two dummy vertices of degree one, and connecting them with v and v', respectively.

from the above reasons in the case of the Hamiltonian first problem is equal to the problem of finding Hamiltonian circuit .

Finally,

Hamiltonian first problem is equivalent to the problem of finding Hamiltonian circuit .

THANK YOU