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)