# Presenters: presenters

 Page 9/9 Date 20.07.2021 Size 249.09 Kb.

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

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

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

## 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