15

Konstrukcja cyklu Eulera. Algorytm Fleury. 
 
Rozwa my  nast puj c   map   wraz  z  odpowiadaj cym  jej  grafem,  Rysunek 

10.  Na 

tym grafie wierzchołki odpowiadaj  obszarom l du a ka dy most jest reprezentowany 
jako kraw d . 
 
 
 
 
 
 
 
 
 
 
 
 
Czy dla grafu z Rysunku 

10 istnieje cykl Eulera? Je li tak, to jak go zbudowa  (tzn. 

poda  ci g kraw dzi). 
Zacznijmy  od  oznaczenia  ka dej  kraw dzi  a 
nast pnie  wybierzmy  jaki   wierzchołek, 
powiedzmy wierzchołek A.  
 
 
 
 
 
 
 

Nast pnie zbudujmy jaki  cykl w grafie G, np. Niech to b dzie cykl 

e

1

e

3

e

2

, 

 
 
 

 

ziemia

 

woda

Rysunek 

10 

B 

D 

C 

A

E 

B 

A 

E

D 

C

B

A

E

D

C 

e

1

 

e

2

 

e

3

 

e

4

 

e

5

 

e

6

 

e

8

 

e

7

 

 

16

Zaznaczamy ten cykl lini  pogrubion . 
 
 
 
 
 
 
 
 
 
 
Nast pnie  zauwa my,  e  pewne  wierzchołki  (wierzchołek  B  i  wierzchołek  C) 

dotykaj   pogrubionych  kraw dzi  wybranego  cyklu 

e

1

e

3

e

2

.  Zatem,  zaczynaj c  od 

wierzchołka  B  budujemy  cykl 

e

4

e

5

.  Cykl  ten  zaznaczony  jest  lini   przerywan . 

Widzimy,  e oba cykle mo emy poł czy  w jeden cykl np. zaczynaj c w wierzchołku 

D mamy cykl 

e

4

e

1

e

2

e

3

e

5

. Zaznaczamy go lini  pogrubion . 

 
 
 
 
 
 
 
 
 
 
 
Widzimy,  e cykl o pogrubionych kraw dziach dotyka pewne pozostałe wierzchołki 
grafu,  np.  wierzchołek  D.  Zaczynaj c  od  wierzchołka  D  wybieramy  kolejny  cykl 

e

6

e

7

e

7

.  Cykl  ten  doł czmy  do  wcze niej  wyznaczonego  cyklu  i  ostatecznie 

otrzymujemy cykl Eulera: 

e

4

e

1

e

2

e

3

e

5

e

6

e

7

e

8

. 

 

B

A

E

D

C 

e

1

 

e

2

 

e

3

 

e

4

 

e

5

 

e

6

 

e

8

 

e

7

 

B 

A 

E

D 

C 

e

1

 

e

2

 

e

3

 

e

4

 

e

5

 

e

6

 

e

8

 

e

7

 

B 

A 

E

D

e

1

 

e

2

 

e

3

 

e

4

 

e

5

 

e

6

 

e

8

 

e

7

 

 

17

Czasami  znalezienie  cyklu  Eulera,  szczególnie  dla  du ych  grafów  mo e  by  
uci liwe. Istnieje inna, konstruktywna metoda, zwana algorytmem Fleury’ego.  
Niech  G  b dzie  grafem  Eulera  (tzn.  grafem  dla  którego  istnieje  cykl  Eulera).  Cykl 
Eulera dla G mo na znale  w oparciu o nast puj cy zestaw instrukcji: 
 

Algorytm Fleury’ego

. 

1.  Z  dowolnego  wierzchołka  zaczynamy  w drówk   po  G  przechodz c  po 

kraw dziach.  Za  ka dym  razem  wymazujemy  wykorzystan   kraw d . 
Wymazujemy  równie   izolowane  wierzchołki  jakie  si   pojawiaj   z  powodu 
wymazywania kraw dzi.  

2.  Nigdy, o ile nie ma innej mo liwo ci, nie wybieraj kraw dzi b d cej mostem, tzn. 

nie  wybieraj  kraw dzi,  której  wymazanie  spowoduje,  e  graf  przestanie  by  
spójny.  

 
Wypróbujmy ten algorytm dla znalezienia cyklu Eulera dla grafu z Rysunku 

11a.  

 
 
 
 
 
 
 
 
 
 
 

Zacznijmy  w  wierzchołku  V

1

 

i  wybierzmy  najpierw  kraw d  

e

1 

a  nast pnie 

e

3

. 

Wymazuj c  te  kraw dzie  otrzymujemy  graf  z  Rysunku 

11b.  Znajdujemy  si   w 

wierzchołku V

3  

i mamy kilka wyborów nast pnej kraw dzi a mianowicie 

e

2

, 

e

6

, oraz 

e

7

.  Jednak  kraw d  

e

2 

jest  mostkiem  i  zgodnie  z  pkt.  1  algorytmu  maj c  inne 

mo liwo ci nie wybieramy tej kraw dzi. Pow drujmy zatem np. wzdłu  kraw dzi 

e

6

. 

Otrzymujemy graf jak na Rysunku 

11c. 

 

e

7

 

e

8

 

e

6

 

e

5

 

e

4

e

3

 

e

2

e

1

V

1

V

2

 

V

3

 

V

4

 

V

5 

V

6 

e

7

 

e

8

 

e

6

 

e

5

 

e

4

 

e

2

 

V

1

 

V

2

V

3

 

V

4

 

V

5 

V

6

Rysunek 

11a

Rysunek 

11b

 

18

Obecnie  mo emy  wybra   w  kolejno ci 

kraw dzie 

e

4

, 

e

5

, 

e

8

,

  e

7

  oraz 

e

2

. 

Przechodz c  wymazujemy  kraw dzie  i 
powstaj ce 

izolowane 

wierzchołki. 

Ka da  z  przechodzonych  kraw dzi  jest 
dla  grafu  z  Rysunku  11c  mostkiem. 
Wybieramy je jednak bo nie mamy innej 
mo liwo ci.  Ostatecznie  wypisujemy 
cał   sekwencj   przebytych  kraw dzi  i 
otrzymujemy  cykl  Eulera  w  postaci: 

e

1

e

3

e

6

e

4

e

5

e

8

e

7

e

2

.  

 
Problem  podobny  do  poszukiwania  cyklu  Eulera  dla  danego  grafu,  polega  na 
odpowiedzi  na  pytanie  czy  istnieje  w  grafie  taki  cykl  w  którym  ka dy  wierzchołek 
jest  odwiedzany  dokładnie  jeden  raz. 

Cykl,  w  którym  ka dy  wierzchołek  jest 

przechodzony  dokładnie  raz  nazywa  si   cyklem  Hamiltona.  Graf  posiadaj cy 
cykl Hamiltona nazywa si  grafem Hamiltona (albo grafem hamiltonowskim).  
Nazwa  pochodzi  od  irlandzkiego 
matematyka  Hamiltona.  Sir  William 
Rowan 

Hamilton 

(1805-1865) 

zaproponował 

gr  

polegaj c  

na 

znalezieniu  cyklu  hamiltonowskiego  w 
grafie obok. 
 
 
 
 
 
 
Wierzchołki  reprezentuj   miasta.  Celem 
gry  było  znalezienie  drogi,  która 
przechodzi przez ka de miasto dokładnie 
jeden raz. 

e

7

 

e

8

 

e

5

 

e

4

 

e

2

 

V

2

 

V

3

 

V

4

 

V

5 

V

6 

Rysunek 

11c 

 

19

Problem cyklu Hamiltona dla danego grafu nie jest do dzi  rozwi zany i stanowi jeden 
z  najpowa niejszych  problemów  w  teorii  grafów.  Do  dzi   nie  ma  twierdzenia 
(podobnego do twierdzenia Eulera), które rozstrzygałoby czy graf jest hamiltonowski. 
Pewien post p został jednak dokonany i znane s  twierdzenia, które podaj  warunki 
pozwalaj ce wykluczy  pewne grafy z klasy grafów hamiltonowskich. U yteczne jest 
np. nast puj ce 
 
Twierdzenie. Je li G jest grafem spójnym o 

3

≥

n

 wierzchołkach i je li  

n

v

u

≥

+

)

deg(

)

deg(

 

dla ka dej pary wierzchołków nie poł czonych kraw dzi  to G jest grafem Hamiltona. 
 
Mocniejszym warunkiem jest zalo enie,  e  w grafem spójnym o 

3

≥

n

 wierzchołkach  

2

)

deg(

n

v

≥  

dla  ka dego  wierzchołka.  Przy  tym  zało eniu  G  jest  grafem  Hamiltona.  Np.  graf  z 
Rysunku  poni ej  spełnia  warunki  twierdzenia 

7

)

deg(

)

deg(

≥

+

v

u

  i  jest  grafem 

Hamiltona. 
 
 
 
 
 
 
 
 
 
Nie spełnia jednak warunku gdy  ma wierzchołki stopnia 3.  
 
Problem  istnienia  cykli  oraz  dróg  Eulera  i  Hamiltona  dla  grafów  ma  powa ne 
znaczenie przy zastosowaniach grafów do rozwi zywania zagadnie  logistycznych.  
 
Twierdzenie  2.  Je li  graf  maj cy  n  wierzchołków  i  nie  maj cy  p tli  ani  kraw dzi 

wielokrotnych ma co najmniej 

2

)

2

)(

1

(

2

1

+

−

− n

n

 kraw dzi to jest hamiltonowski. 

 

20

 
 
 
 
 
 
 
 
 
W  grafie  na  Rys. 

12a  mamy  n=5  wierzchołków  oraz 

8

2

/

)

4

4

3

2

3

(

|

|

=

+

+

+

+

=

E

 

kraw dzi. Graf ten spełnia zało enia twierdzenia. Poniewa  

8

2

2

/

)

2

)(

1

(

=

+

−

− n

n

 i 

jest co najmniej równe liczbie kraw dzi to graf ten jest hamiltonowski. Graf z Rys.12b 
ma tylko 7 kraw dzi i nie spełnia zało enia twierdzenia ale spełnia zało enia naszego 
pierwszego twierdzenia o sumie stopni par wierzchołków nie poł czonych kraw dzi . 
Jest to wi c równie  graf hamiltonowski.  
 
Twierdzenie Eulera powoduje,  e teoria cykli Eulera jest zgrabna i kompletna. Czego 
mo na  dowie   o  cyklach  Hamiltona?  W  pewnych  warunkach  graf  ma  tak  du o 
kraw dzi w stosunku do liczby wierzchołków,  e musi w nim istnie  cykl Hamiltona.  
Jednak wida ,  e np. graf (a) z Rysunku obok ma mało kraw dzi a jest hamiltonowski. 
Graf (b) ma du o kraw dzi i nie ma cyklu Hamiltona.  
 
 
 
 
 
 
 
Poznane twierdzenia nie s  zadawalaj ce nie tylko w tym sensie,  e podane warunki 
wystarczaj ce nie s  konieczne ale te  nie daj   adnych wskazówek jak znale  cykl 
Hamiltona.  Poj cie  cyklu  Eulera  wydaje  si   by   bardzo  bliskie  poj ciu  cyklu 
Hamiltona,  jednak  teoria  cykli  Hamiltona  jest  znacznie  bardziej  zło ona.  W 
szczególno ci nie jest znany  aden efektywny algorytm znajdowania cykli Hamiltona. 

Rysunek 

12 

(a) 

(b) 

(a)

 

(b)