W5.PDF

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

{

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 .

010 000

110

11 00

10 00

100

111

101

10 01

11 01

011 001

(a)

(b)

(c)

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 hipe rkostkach (n-wymiarowych

sze cianach). Kwadrat i sze cian to hiper kostki 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.

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 .

K 2,2

K 3,2

K 3,3

(a)

(b) (c)

(d)

Rysunek 13

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.

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.

Rysunek 14

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

4 drzewa spinaj ce grafu H

Rysunek 15

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

Wszystkie one maj po 6 kraw dzi.

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.

Ilustracja Twierdzenia 5.

e 1

e 2

e 5

e 7

e 1

e 2

e 5

e 7

e 3

e 4

e 6

e 8

e 10

e 3

e 4

e 6

e 8

e 10

e 9

Rysunek 16

(a)

(b)

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.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: