Presenters: presenters

Download 249.09 Kb.

Page	9/9
Date	20.07.2021
Size	249.09 Kb.
	#57089

1 2 3 4 5 6 7 8 9

roll-25-29

EXAMPLES

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).

But the graph G3 has neither Hamiltonian circuit nor a Hamiltonian path.

More examples

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:

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:

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:

Multi-threshold 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 power-gated domain during its sleep-to-active 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 Hamiltonian-cycle routing to serially connect all the power switches

APPLICATION

Anything where you have to visit all locations, such as

pizza delivery

mail delivery

traveling salesman

garbage pickup

bus service/ limousine service

reading gas meters

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.

KTM-BHAKTPUR-HETAUDA-BIRGUNJ-POKHARA=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 !!!

Download 249.09 Kb.

Share with your friends:

1 2 3 4 5 6 7 8 9