Question

Explain how backtracking can be used to find a Hamilton path or circuit in a graph.

Short answer

By using the backtracking process, it can get Hamilton path circuit in a graph.

Step-by-step solution

Definition

A Hamilton path is a straightforward path that precisely traverses each vertex one time.

A Hamilton circuit is a straightforward circuit that only makes one complete pass through each vertex.

Explanation by Hamilton circuit.

Let us a connected graph G having vertices\({\bf{(}}{{\bf{v}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{2}}}{\bf{,}}....{{\bf{v}}_{\bf{n}}}{\bf{)}}\).

Let the path is P.

Let’s assume that path starts from\({{\bf{v}}_{\bf{1}}}\). Repeatedly add an edge from the end of the path to a vertex not yet included in the path or to\({{\bf{v}}_{\bf{1}}}\). It is no longer possible to extend the path and if all vertices are not included in the path P. Then backtrack to the last vertex in the path P that contains a different edge to vertex not yet included in the graph. If it manages to return to, then it gets a Hamilton circuit.

Result for Hamilton path

Let us a connected graph G having vertices.

Let the path is P.

Let’s assume that path starts from\({{\bf{v}}_{\bf{1}}}\) .Repeatedly add an edge from the end of the path to a vertex not yet included in the path or to. It is no longer possible to extend the path and if all vertices are not included in the path P, then backtrack to the last vertex in the path P that contains a different edge to vertex not yet included in the graph. If it manages to obtain a path of length n-1, then it gets a Hamilton path.

Therefore, by using the backtracking results It gets the require result.