[go: up one dir, main page]
Scribd
Upload
314 views3 pages

Hamiltonian Graph Example

A Hamiltonian graph is a connected graph that contains a Hamiltonian circuit, which is a closed walk that visits each vertex exactly once except for the starting vertex without repeating any edges. An example graph shows a Hamiltonian circuit ABCDEFA. A Hamiltonian path is similar but is not a closed walk - it visits each vertex exactly once without repeating edges but may not use all the edges of the graph.

Uploaded by

FY20H817 Abhijeet Bhushari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
314 views3 pages

Hamiltonian Graph Example

A Hamiltonian graph is a connected graph that contains a Hamiltonian circuit, which is a closed walk that visits each vertex exactly once except for the starting vertex without repeating any edges. An example graph shows a Hamiltonian circuit ABCDEFA. A Hamiltonian path is similar but is not a closed walk - it visits each vertex exactly once without repeating edges but may not use all the edges of the graph.

Uploaded by

FY20H817 Abhijeet Bhushari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Hamiltonian Graph-

A Hamiltonian graph may be defined as-

If there exists a closed walk in the connected graph that visits every vertex of the graph exactly
once
(except starting vertex) without repeating the edges,
then such a graph is called as a Hamiltonian graph.
OR
Any connected graph that contains a Hamiltonian circuit is called as a Hamiltonian Graph.

Also Read- Euler Graph

Hamiltonian Graph Example-

The following graph is an example of a Hamiltonian graph-

Here,
• This graph contains a closed walk ABCDEFA.
• It visits every vertex of the graph exactly once except starting vertex.
• The edges are not repeated during the walk.
• Therefore, it is a Hamiltonian graph.

Alternatively, there exists a Hamiltonian circuit ABCDEFA in the above graph, therefore
it is a Hamiltonian graph.

Hamiltonian Path-

• If there exists a walk in the connected graph that visits every vertex of the graph
exactly once without repeating the edges, then such a walk is called as a
Hamiltonian path.
OR
• If there exists a Path in the connected graph that contains all the vertices of the
graph, then such a path is called as a Hamiltonian path.

NOTE
In Hamiltonian path, all the edges may or may not be covered but edges must not repeat.

Hamiltonian Path Examples-

Examples of Hamiltonian path are as follows-

You might also like