In this tutorial we shall learn about Hamiltonian graph.
Definition:
A graph that contains Hamiltonian circuit is called as Hamiltonian graph.
What is Hamiltonian circuit?
A path that passes through every vertex exactly once is called as Hamiltonian circuit. It should return to the original starting vertex.
Example:
Now we have to find if we have a Hamiltonian circuit?
If we traverse a -> b -> c -> d -> e -> a
We have a Hamiltonian path. Hence the graph is a Hamiltonian graph.
This is a NP complete problem. There is no polynomial solution.
Hamiltonian Path:
If there is a path that starting from a vertex and visits all the vertices, but cannot return to the initial vertex. This is called as Hamiltonian path.
Example:
If we follow the path a -> b -> c -> d -> e. Here we visited all the vertices only once, but cannot return to the initial vertex. This is called as Hamiltonian path.