Presenters: presenters


Identifying Euler circuits and Euler paths



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

Identifying Euler circuits and Euler paths:

Identifying Euler circuits and Euler paths:

Undirected graphs:

  • The graph G 1 has an Euler circuit, for example a,e,c,d,e,b,a .
  • The graph G2 has neither an Euler circuit nor an Euler path.
  • The graph G3 doesn’t have an Euler circuit but it has an Euler path, namely, a,d,c,e,b,c,a,b .

a

b

d

c

G1

a

d

e

c

b

G2

a

b

d

c

G3

e

Directed graphs:

Directed graphs:

  • The graph H1 has an Euler path, namely d,a,b,d,c,b .
  • The graph H2 has an Euler circuit, namely, a,g,c,b,g,e,d,f,a.

d

c

b

a

H1

a

b

c

d

e

f

g

H2

Theorem 1: A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree.


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