EXAMPLES
a
b
c
d
e
a
b
c
d
G1
G2
 Graph G1 has a Hamiltonian circuit (a,b,c,d,e,a).
 Graph G2 has no Hamiltonian circuit but a Hamiltonian path (a,b,c,d).
a
b
c
d
e
f
g
 But the graph G3 has neither Hamiltonian circuit nor a Hamiltonian path.
G3
CONDITIONS  A vertex should be of degree 2 at minimum.
 If a node has degree two then both edges must be a part of any Hamiltonian circuit.
 A Hamiltonian circuit cannot contain smaller circuit within it.
Special Case:  A circuit of n vertices is a Hamiltonian circuit if n>=3.
Dirac’s Theorem If G is a simple graph with n vertices with n>=3 such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit. Example:
a
b
c
d
G
In graph G:
No. of vertices= 4
Therefore, n/2=4/2=2
Degree of vertices:
deg(a)=3, deg(b)=3, deg(c)=3, deg(d)=3
Here, degree of each vertex is at least n/2.
Thus from Dirac’s theorem, G has a Hamilton circuit i.e. a,b,c,d,a.
ORE’S Theorem If G is a simple graph with n vertices with n>=3 such that deg(u)+deg(v)>=n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit. Example:
a
b
c
d
G
In graph G:
No. of vertices=4
Degree of vertices:
deg(a)=1, deg(b)=3, deg(c)=2, deg(d)=2
Here nonadjacent vertices pairs are (a,c), (a,d).
Then, deg(a)+deg(c)=3 (
deg(a)+deg(d)=3 (
Thus, from ORE’s Theorem, G doesn’t have a Hamilton circuit.
APPLICATION  Electronic circuit design/construction:
Multithreshold CMOS (MTCMOS) is currently the most popular methodology in industry for implementing a power gating design, which can effectively reduce the leakage power by turning off inactive circuit domains. However, large peak current may be consumed in a powergated domain during its sleeptoactive mode transition. As a result, major IC foundries recommend turning on power switches one by one to reduce the peak current during the mode transition, which requires a Hamiltoniancycle routing to serially connect all the power switches APPLICATION Anything where you have to visit all locations, such as Famous Travelling Salesman Problem  Let a salesman want to visit the cities as mentioned above. In which order should he visit these cities to travel minimum total distance?
113
133
56
167
137
147
135
58
98
BIRGUNJ
KTM
HETAUDA
POKHARA
BHAKTAPUR
The given figure contain different ways to visit all the cities.
The most straightforward way to solve an instance of the travelling salesman problem is to examine all the possible Hamilton circuits and select one of minimum total length.
For the above problem to visit all the cities with minimum length we have to follow these path.
KTMBHAKTPURHETAUDABIRGUNJPOKHARA=458
Except this all other path are long. This is the shortest Hamilton path to solve the given salesman problem.
summary
PROPERTIES

EULERIAN

HAMILTONIAN

1.Repeated visit to given node allowed?

YES

NO

2. Repeated travel of edge allowed?

NO

NO

3. Omitted nodes allowed?

NO

NO

4. Omitted edges allowed?

NO

YES
 Thank you !!!
Share with your friends: 