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