Presenters: presenters



Download 249.09 Kb.
Page9/9
Date20.07.2021
Size249.09 Kb.
1   2   3   4   5   6   7   8   9

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

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:


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:
  • 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

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




The database is protected by copyright ©ininet.org 2020
send message

    Main page