21

Zastosowania cykli Hamiltona - Kod Gray’a.

Kod Gray’a długo ci n jest to ci g wszystkich 2

n

ró nych ci gów n cyfr dwójkowych,

ustawionych w ten sposób, e dwa kolejne ci gi ró ni si dokładnie jedn cyfr oraz
ostatni ci g ró ni si dokładnie jedn cyfr od pierwszego ci gu. Np. 00, 01, 11, 10 jest
ci giem Graya długo ci 2.
Konstrukcj kodu Graya mo na widzie jak problem z teorii grafów. Niech V(G) b dzie

zbiorem

n

}

1

,

0

{

wszystkich ci gów cyfr dwójkowych długo ci n. Poł czmy ci gi u i v

kraw dzi , je li u i v ró ni si dokładnie jedn cyfr .











Kod Graya długo ci n jest w istocie cyklem Hamiltona w grafie G. Na Rysunku

(a) jest

pokazany graf dla n=2. Rysunek

(b) przedstawia ten sam graf narysowany w inny

sposób. Graf ten ma dwa cykle Hamiltona, po jednym w ka dym kierunku, co pokazuje,

e istniej dwa (w zasadzie równowa ne) ci gi Graya długo ci 2. Na Rysunku

(c) jest

pokazany graf dla n=3. Istnieje 12 kodów Graya długo ci 3. Rysunek (c) pokazuje cykl
Hamiltona odpowiadaj cy jednemu z tych kodów.
Kodów Graya u ywa si do etykietowania obiektów na hiperkostkach (n-wymiarowych
sze cianach). Kwadrat i sze cian to hiperkostki odpowiedni 2 i 3 wymiarowe.

Wierzchołki grafów skonstruowanych w trakcie budowy kodu Graya mog by
podzielone na dwa zbiory, tych, które maj parzyst liczb jedynek i tych z nieparzyst
liczb jedynek. Podział ten jest taki, e ka da kraw d ł czy element jednego zbioru z
elementem drugiego. Jest to przykład grafu dwudzielnego.

10 01

11 00

11 01

10 00

011 001

010 000

111

101

110

100

(a)

(b)

(c)

22

Graf G nazywamy

grafem dwudzielnym, je li zbiór V(G) jest sum dwóch niepustych

zbiorów rozł cznych V

1

i V

2

takich, e ka da kraw d w grafie G ł czy wierzchołek ze

zbioru V

1

z wierzchołkiem ze zbioru V

2

.

Graf nazywamy

pełnym grafem dwudzielnym, je li ponadto ka dy wierzchołek zbioru

V

1

jest poł czony z ka dym wierzchołkiem zbioru V

2

dokładnie jedn kraw dzi .

Wszystkie grafy pokazane na Rysunku

13 s grafami dwudzielnymi. Wszystkie oprócz

grafu (b) s pełnymi grafami dwudzielnymi.

Dla danych liczb m i n wszystkie pełne grafy dwudzielne takie, e |V

1

|=m i |V

2

|=n, s

izomorficzne; oznaczmy je

K

m,n

. Zauwa my, e grafy

K

m,n

i

K

n,m

s izomorficzne.

Twierdzenie 3. Niech G b dzie grafem dwudzielnym i niech b dzie podziałem jego
wierzchołków. Je li graf G ma cykl Hamiltona, to |V

1

|=|V

2

|. Je li graf ma drog

Hamiltona, to liczby |V

1

| i |V

2

| ró ni si co najwy ej o 1.

K

2,2

K

3,2

K

3,3

(a)

(b) (c)

(d)

Rysunek

13

23

Drzewa.

Przedstawimy teraz pewne wiadomo ci dotycz ce grafów, które s acykliczne i spójne;
nazywamy je

drzewami. Rysunek 14 podaje przykłady drzew. Przykładami drzew s

grafy z poni szego Rysunku.







Dla danego grafu spójnego interesuje nas minimalny podgraf ł cz cy wszystkie
wierzchołki. Taki podgraf musi by acykliczny, gdy mo na usun jedn kraw d
dowolnego cyklu, nie trac c przy tym własno ci spójno ci.

Drzewo spinaj ce: minimalny podgraf T grafu G ł cz cy wszystkie wierzchołki grafu
G. Drzewo T zawiera wszystkie wierzchołki grafu G, tzn. V(T)=V(G).











Graf H z Rysunku

15 ma ponad 300 drzew spinaj cych, 4 z nich zostały pokazane.

Wszystkie one maj po 6 kraw dzi.

H

4 drzewa spinaj ce grafu H

Rysunek

15

Rysunek

14

24

Twierdzenie 4. Niech e b dzie kraw dzi grafu spójnego G. Nast puj ce warunki s
równowa ne:
a) graf G\{e} jest spójny;
b) e jest kraw dzi w pewnym cyklu w grafie G;
c) e jest kraw dzi w pewnej zamkni tej drodze prostej w grafie G.

Szkic dowodu.
a) Je li e jest p tl to: graf G\{e} jest spójny i sama kraw d e jest cyklem. Poniewa

cykle s zamkni tymi drogami prostymi to twierdzenie jest w tym przypadku
prawdziwe.

b) Przyjmijmy, e e jest kraw dzi i ł czy dwa ró ne wierzchołki u i v. Je li istnieje

inna kraw d f ł cz ca u i v to graf G\{e} jest spójny i ci g ef jest cyklem
zawieraj cym e. Twierdzenie jest prawdziwe w tym przypadku.

c) Pominiemy dowód ostatniego przypadku gdy e jest

jedyn kraw dzi i ł cz c dwa

ró ne wierzchołki u i v.

Twierdzenie 5. Ka dy sko czony graf spójny ma drzewo spinaj ce.


Dowód. We my spójny podgraf G’ grafu G zawieraj cy wszystkie wierzchołki G i
maj cy najmniejsz mo liw liczb kraw dzi. Przypu my, e graf G’ zawiera cykl, do
którego nale y np. kraw d e. Z twierdzenia 4 wynika, e graf G’\{e} jest spójnym
podgrafem grafu G i ma mniej kraw dzi ni G’, co jest sprzeczne z wyborem G’. Zatem
graf G’ nie ma cykli. Poniewa jest spójny to jest drzewem.

25

Ilustracja Twierdzenia 5.







a) Rozwa my graf spójny z Rysunku

16a. Kraw d e

1

nie nale y do adnego cyklu;

graf G\{

e

1

} nie jest spójny bo adna droga w G\{

e

1

} nie ł czy wierzchołka v z

innymi wierzchołkami. Podobnie kraw d

e

5

nie nale y do adnego cyklu i graf

G\{

e

5

} nie jest spójny. Pozostałe kraw dzie nale do cykli. Po usuni ciu dowolnej z

nich graf pozostaje spójny.

b) Zauwa my, e graf G\{

e

10

} jest nadal spójny, ale ma cykle. Je li usuniemy równie

kraw d e

8

to otrzymany graf G\{

e

10

,e

8

} nadal b dzie miał cykl, mianowicie

e

2

e

3

e

4

.

Gdy usuniemy jedn z kraw dzi w tym cyklu np. e

4

to otrzymamy acykliczny graf

spójny, czyli drzewo spinaj ce. (Rysunek

16b).

Mo na w ten sposób otrzyma ró ne drzewa spinaj ce.

Charakteryzacja drzew nie traci na ogólno ci je li rozwa amy tylko drzewa bez p tli i
kraw dzi wielokrotnych.

Twierdzenie 6. Niech G b dzie grafem bez p tli i kraw dzi wielokrotnych, maj cym
wi cej ni jeden wierzchołek. Nast puj ce warunki s równowa ne:
a) G jest drzewem;
b) Ka de dwa ró ne wierzchołki s poł czone dokładnie jedn drog prost ;
c) Graf G jest spójny, ale przestaje by spójny po usuni ciu dowolnej kraw dzi;
d) Graf G jest acykliczny, ale przestaje by acykliczny po dodaniu jakiejkolwiek

kraw dzi.

Aby doceni Twierdzenie 6 popatrzmy na przykład na drzewa z Rysunków

14-16.

Ka de z nich ma własno ci a) – d). Je li rozwa ymy dowolny graf nie b d cy drzewem
to zauwa ymy, e nie ma on adnej z tych własno ci.

v

e

1

e

2

e

5

e

3

e

4

e

6

e

7

e

8

e

9

e

10

v

e

1

e

2

e

5

e

3

e

4

e

6

e

7

e

8

e

9

e

10

Rysunek

16

(a)

(b)

26

Problem minimalnej poł czeniowo ci – minimalne drzewo spinaj ce.

Jednym z najwa niejszych zagadnie spotykanych w problemach opisywanych przez
grafy nieskierowane jest problem znalezienia minimalnego drzewa spinaj cego.

Przykład. Przypu my, e mamy poł czy sieci autostrad nast puj ce miasta:














Liczby przypisane kraw dziom grafu na Rysunku 17b oznaczaj koszt wybudowania
autostrady mi dzy miastami poł czonymi dan kraw dzi . Np. koszt budowy autostrady
pomi dzy A i B wynosi 15 jednostek (powiedzmy 150 mln. PLN).

Nie sta nas jednak na budow wszystkich autostrad st d pojawia si pytanie:
które autostrady nale y zbudowa aby zachowa poł czenia mi dzy wszystkimi
miejscowo ciami a koszt budowy był minimalny.
Jest to problem tzw. minimalnego drzewa spinaj cego.

Definicja.

Niech G oznacza nieskierowany graf spójny.

Drzewo spinaj ce, które ma

najmniejsz wag po ród wszystkich mo liwych drzew spinaj cych nazywa si
minimalnym drzewem spinaj cym.

A

B

C

D

E

A

B

C

D

E

12

20

32

18

15

20

17

22

Rysunek 17a

Rysunek 17b

27

Istnieje kilka algorytmów wyznaczaj cych minimale drzewo spinaj ce dla danego
grafu. Zapoznamy si z jednym z nich.

Algorytm Kruskala.

Niech G oznacza nieskierowany graf spójny, w którym ka da kraw d ma nieujemn
wag . Nast puj cy algorytm wyznacza minimalne drzewo spinaj ce grafu G:
1) Wybierz na grafie G kraw d z najmniejsz wag .
2) Kontynuuj wybieranie kraw dzi o minimalnych wagach pod warunkiem, e za

ka dym razem wybierasz kraw d , która nie tworzy p tli z adn z wcze niej
wybranych kraw dzi.

3) Je li nie mo na ju wybra adnej kraw dzi bez naruszenia warunku 2 to otrzymane

drzewo jest minimalnym drzewem spinaj cym dla G.

Przykład.
Minimalne drzewo spinaj ce dla grafu:









Wybieramy kraw d o najmniejszej wadze. Jest ni kraw d e3 (lub e9).

e5

e1

e3

e2

e4

e6

e7

e8

e9

e10

5

5

0

4

6

8

2

4

0

5

e1

e3

e2

e4

e6

e5

e7

e8

e9

e10

5

5

0

4

6

8

2

4

0

5

28

Teraz wybieramy e9 jako kraw d o najmniejszej wadze po ród kraw dzi jakie nam
pozostały







a nast pnie kraw d e7







Na tym etapie mamy mamy do wyboru dwie kraw dzie o najmniejszej wadze e2 oraz
e8. Zauwa my jednak, e wybór kraw dzi e8 pogwałci warunek (2) algorytmu, gdy
kraw d ta tworzy cykl z ju wybranymi kraw dzimi e7 i e9. Tak wi c wybieramy e2.







Dalsze etapy to wybór e1 i ostatecznie e5 (nie wybramy e10 bo tworzy p tl z e9).
Szukane minimalne drzewo spinaj ce ma posta :

e1

e3

e2

e4

e6

e5

e7

e8

e9

e10

5

5

0

4

6

8

2

4

0

5

e1

e3

e2

e4

e6

e5

e7

e8

e9

e10

5

5

0

4

6

8

2

4

0

5

e1

e3

e2

e4

e6

e5

e7

e8

e9

e10

5

5

0

4

6

8

2

4

0

5

e1

e3

e2

e4

e6

e5

e7

e8

e9

e10

5

5

0

4

6

8

2

4

0

5