Ws zechnica Popołudniowa

Znajdowanie najkróts zych dróg ora z najniżs zych i najkróts zych drzew

prof. dr hab. Maciej M Sysło

prof. dr hab. Maciej M Sysło

Zes zyt dydaktyczny opracowa ny w ramach projektu edukacyjnego

— ponadregionalny program rozwija nia kompetencji

uczniów s zkół ponadgimna zjalnych w zakresie technologii
informacyjno-komunikacyjnych (ICT).

Wars zawska Wyższa Szkoła Informatyki

ul. Le wartows kiego 17, 00-169 Wars zawa

Projekt graficzny: FRYCZ I WICHA

Warsza wa 2010
Copyright © Wars zawska Wyższa Szkoła Informatyki 2010
Publikacja nie jes t przeznaczona do sprzedaży.

Uniwers ytet Wrocławski, UMK w Toruniu

s [e-mail], [e-mail]

< 4 >

Informatyka +

Wykład jes t poś więcony elementom teorii gra fów i obliczeń na gra fach. Grafy odgrywają podwójną rolę w in-
formatyce. Z je dnej strony, s ą modelami obliczeń – w tej roli najczę ściej wys tępują drzewa – lub odzwiercie -
dlają s trukturę połączeń komunikacyjnych, a z drugiej – wiele problemów o praktycznych zas tos owaniach
jes t definiowanych na grafach jako s trukturach połączeń (zależności) między elementami. W pierws zej czę -
ści wykładu zos taną przeds tawione problemy, które miały wpływ na rozwój teorii grafów ora z dużą ich popu-
larność. Druga częś ć jes t poś więcona wykorzys taniu drze w jako schematów obliczeń i algorytmów, a w trze -
ciej częś ci zos taną przeds tawione klas yczne problemy obliczeniowe na grafach, takie jak: znajdowa nie naj-
krótszych dróg i znajdowanie najkrótszego drzewa rozpina jącego w gra fie z obcią żonymi połączeniami. Roz-
wią za nia problemów bę dą prezentowane w s pecjalnym oprogramowaniu.

1. Grafy jako modele różnych s ytuacji ............................................................................................................. 5

2. Trzy kla s yczne zagadnienia ......................................................................................................................... 6

2.1. Grafy Eulera .......................................................................................................................................... 6

2.2. Malowanie map .................................................................................................................................... 7

2.3. Grafy Hamiltona i problem komiwoja żera ............................................................................................. 8

3. Przykłady za s tos owań grafów w informat yce ............................................................................................ 10

3.1. Drzewa wyrażeń ................................................................................................................................. 10

3.2. Drzewa a lgorytmów .............................................................................................................................11

3.3. Drzewa Huffmana – krótkie kody ........................................................................................................ 12

4. Algorytmy na grafach ................................................................................................................................ 13

4.1. Grafy i ich komputerowe reprezentacje ............................................................................................... 14

4.2. Znajdowanie najkrótszych dróg w grafach .......................................................................................... 15

4.3. Znajdowanie najkróts zych drzew rozpinają cych w grafach .................................................................. 16

Literatura ....................................................................................................................................................... 17

> Znajdowanie najkrótszych dróg oraz najniższych i najkrótszych drzew

< 5 >

Ten wykład je st poś wię cony gra fom i ich zas tos owaniom. W potocznym s ensie grafem jes t pewien zbiór ele -
mentów, mię dzy którymi is tnieją połączenia. Na przykład, mia s ta i s ieć połą czeń mię dzy nimi tworzą graf. Po-
łączeniami z kolei mogą być drogi dla s amochodów, sie ć połączeń kolejowych lub s ieć połączeń lotniczych.
Na rys unku 1 s ą przedstawione fragmenty połą czeń lotniczych. W rozwa żaniach informatycznych (algoryt-
micznych) na ogół nie intere suje na s , czemu odpowiadają elementy w takich sieciach połączeń (mia s ta , s ta -
cje, lotniska) i jaki jes t charakter połączeń (drogowy, kolejowy, lotniczy). Elementy w takich sieciach połączeń
na zywamy wierzchołkami, połączenia – krawędziami (jeśli s ą s ymetryczne, czyli nieskierowane) lub łukami
(jeśli s ą skierowane), a sie ć – grafem (gdy za wiera s ymetryczne połączenia) lub digrafem (gdy zawiera skie -
rowane połączenia). Graf jes t modelem s ytuacji, w której mamy zbiór elementów i połączenia mię dzy nimi.

Rysunek 1.
Przykład sieci połączeń lotniczych z Bydgos zczy

Na rysunku 2 przeds tawiono inny przykład pojawiania się grafów. Jes t on zwią zany z Eulerem, który rozwa -
żał s iatki wielościanów, czyli grafy utworzone z wierzchołków i kra wę dzi wieloś cianów – s tąd pochodzą na-
zwy wierzchołek i krawędź.

Rysunek 2.
Sześ cian i graf jego siatki. Wierzchołki sze ścianu s ą wierzchołkami grafu, a krawę dzie s ześ cianu s ą krawę -
dziami grafu. Dwa inne przykłady s ze ścianów s ą poka zane obok

Elementarnym wprowadzeniem do teorii grafów jes t ksią żka [8]. Za s tosowania gra fów w informatyce zilustro-
wano w ksią żkach [2], [5], [6]. Grafy zwią zane z zagadka mi można znaleźć w [6]. Głębs ze rozwa żania na tema t
grafów i ich algorytmów zamies zczono w ksią żkach [1], [3], [7].

W rozdziale 2 przytaczamy najbardziej zna ne przykłady zwią zane z grafami, które przyczyniły s ię do ich po-
pularności i wzros tu zainteresowania nimi. W rozdziale 3 ilustrujemy pos łużenie się drzewami – specjalnymi
rodzajami gra fów, które mają duże zas tos owania w informa tyce , a dokładniej – w kons trukcji i analizie algo-
rytmów. Na tomias t w rozdzia le 4 przeds ta wiamy kilka problemów i algorytmów zwią zanych z dowolnymi gra -

< 6 >

Informatyka +

fami. Rozwa żania na wykładzie będą ilus trowane za pomocą oprogramowania edukacyjnego, które s łuży do
demons tracji dzia łania algorytmów na grafach i ich komputerowych realiza cji.

Przeds tawiamy tutaj trzy przykłady klas ycznych zagadnień, które uwa ża się, że najbardziej przyczyniły s ię do
olbrzymiej popularnoś ci grafów jako modeli różnych s ytuacji.

Wspomniany już wcześniej Leonhard Euler (1707-1783) je st uwa żany za ojca teorii grafów. W roku 1736, gdy
mies zkał w obe cnym Kaliningradzie (Rosja), zainteres ował s ię, czy można zorganizowa ć wycie czkę po tym
mieś cie w taki s pos ób, aby przejś ć ka żdy mos t na rzece Pregoła, ka żdy dokładnie je den ra z. Zagadka ta nosi
na zwę mostów królewieckich, gdyż Kaliningrad przez jakiś czas od połowy XV wieku nosił na zwę Królewiec;
za cza s ów Eulera zaś na zywał się Königs berg. Na rysunku 3, na s tarej mapie te go mias ta z czas ów Eulera , na-
niesiono wspomniane w zagadce mos ty, było ich siedem.

Rysunek 3.
Rzeka Pregoła w Königsberg z za znaczonymi na niej mos tami (białe grube kreski), a obok graf (dokładniej –
multigraf) odpowia dający tej s ytuacji

Zagadkę Eulera można przetłumaczyć na ję zyk innej zagadki, w której pytamy, czy daną figurę można na ry-
sować na kartce papieru be z odrywania ołówka przechodząc ka żdą linię dokładnie jeden ra z. Taka figura na-
zywa s ię jednobie żną lub unikurs alną. Ła two zauwa żyć, że w ka żdym wierzchołku takiej figury liczba połą -
czeń, którymi wchodzimy do wierzchołka musi być równa liczbie połączeń, którymi wychodzimy z tego wierz-
chołka , a więc liczba połączeń w ka żdym wierzchołku – tę liczbę na zywamy s topnie m wierzchołka – musi
być parzys ta , jeś li mamy powrócić do punktu startu, lub graf może zawierać dokładnie tylko dwa wierzchołki
o s topniach nieparzys tych, wtedy droga zawierająca wszys tkie połączenia musi się zaczynać i kończyć w tych
wierzchołkach. W pierws zym przypadku, graf zawiera cykl Eulera , a w drugim – drogę Eulera . Graf zawiera ją-
cy cykl Eulera na zywamy grafem Eulera . Ła two s pos trzec, że graf mos tów królewieckich na rys . 3 nie je st jed-
nobie żny, gdyż ws zys tkie jego cztery wierzchołki mają s topnie nieparzys te.

Rysunek 4.
Odpowiedz, która z figur jes t jednobieżna?

> Znajdowanie najkrótszych dróg oraz najniższych i najkrótszych drzew

< 7 >

W połowie XIX wieku w Anglii duże zainteres owanie wzbudził Proble m Czerech Kolorów, który prze z ponad
s to lat był Przypus zczeniem Cztere ch Kolorów. Ten problem, ja k więks zoś ć problemów dotyczących grafów,
ma bardzo pros te s formułowa nie. Bierzemy mapę na przykład mapę Polski z podzia łem adminis tracyjnym
i chcemy tak pomalować województwa kolorami, by żadne dwa są siadujące ze s obą województwa nie zos tały
pomalowa ne tym s amym kolorem, s taramy s ię przy tym użyć możliwie jak najmniejs zej liczby kolorów. Fran-
cis Guthrie , s tudent De Morga na, w 1852 roku pos ta wił przypus zczenie, że zaws ze cztery kolory wys tarczą.

Zwią zek Problemu Czterech Kolorów z grafami jes t zilus trowany na rysunku 5. Najpierw tworzymy graf, któ-
ry bę dzie odzwiercie dlał s ąs iedztwo województw. A za tem wierzchołki w tym grafie mogą odpowia dać s toli-
com woje wództw i dwa wierzchołki połączymy krawędzią , jeśli odpowiadające im województwa bezpośre d-
nio graniczą ze sobą . Zauwa żmy, że w tak utworzonym grafie, żadne dwie krawę dzie nie przecinają się poza
wierzchołkami – graf, który można tak narys ować, na zywa się grafem planarnym, a jego rysunek – grafem
płas kim. Specyfikacja Problemu Cztere ch Kolorów dla grafów ma tera z na s tępującą pos tać:

Problem Czterech Kolorów dla grafów
Dane:

Graf planarny G.

Wynik: Pomalowanie wierzchołków grafu G co najwyżej 4 kolorami w taki spos ób, że żadne dwa wierzchoł-

ki połączone krawędzią, nie zos ta ły pomalowane tym s amym kolorem.

Rysunek 5.
Mapa polski z podziałem na województwa. Na mapie naniesiono połączenia odpowiadające s ą siedztwu wo-
jewództw. Obok graf województw i je go pokolorowanie czterema kolorami (kolory s ą oznaczone liczbami
1, 2, 3, 4)

Wróćmy do ma lowania grafu woje wództw (patrz rys. 5). Wierzchołki tego grafu pomalowaliśmy 4 kolorami
(oznaczonymi liczba mi 1, 2, 3, 4) s tosując algorytm, w którym wierzchołki są malowane w kolejnoś ci s topni,
od najwięks zego i malowanemu wierzchołkowi dajemy kolor o możliwie najmniejs zej liczbie. W taki spos ób,
najpierw Poznań (s ą siaduje z 7 województwami) otrzyma ł kolor 1, później Łódź (s ąs iaduje z 6 województwa-
mi) otrzyma ła kolor 2, na s tępnie Wars zawa otrzymała kolor 1, Kielce – kolor 3, Bydgos zcz – kolor 3, Gdańsk
– kolor 2, Ols ztyn – kolor 4, Lublin – kolor 2, Katowice – kolor 1, Opole – kolor 3, Szczecin – kolor 3, Biały-
s tok – kolor 3, Rzes zów – kolor 1, Kraków – kolor 2, Wrocław – kolor 2, Zielona Góra – kolor 4. Jako ćwiczenie
proponujemy sprawdzenie, czy ten graf nie można pomalowa ć trzema kolorami.

Za s tosowany przez na s algorytm malowania grafu to algorytm s ekwencyjny, który może być s tos owany do
malowa nia wierzchołków dowolnego grafu. Stos owana jes t w nim s trategia zachłanna – na ka żdym kroku
jes t używany możliwie najmniejs zy kolor. Problem kolorowania grafów jes t bardzo trudny algorytmicznie –
więcej szczegółów na temat tego problemu można znaleźć w ksią żkach [8] i [7].

< 8 >

Informatyka +

Wróćmy jes zcze do his torii Problemu Cztere ch Kolorów. W 1879 roku Alfred B. Kempe opublikował dowód, że
ka żdy graf planarny można pomalować co najwyżej 4 kolorami. Je dnak w 1890 roku Percy J. Heawood znala zł
błąd w dowodzie Kempego, ale był w s tanie udowodnić, że 5 kolorów wys tarczy dla grafów pla narnych (do-
wód jes t bardzo pros ty – patrz [8]). Przez niemal 100 la t tym problemem interesowali się niemal ws zys cy ma-
tematycy, rozwijają c wiele różnych me tod, a ż dopiero w 1976 roku Przypus zczenie Czterech Kolorów zos ta ło
potwierdzone przez … komputer. Dokonali tego Kenneth Appel i Wolfgang Haken przy współpracy z progra-
mis tą Johnem Kochem. Komputer pracowa ł prze z 1200 godzin. Dotychcza s nie udało s ię podać dowodu te go
twierdzenia, który nie korzystałby z komputera.

Bardzo podobnie do problemu Eulera z punktu 2.1 brzmi problem pos tawiony w 1859 roku prze z Williama R.
Hamiltona (1805-1865). W tym przypadku, zagadka dotyczyła dwuna s tościanu formalnego i nale żało znaleźć
drogę zamknię tą przechodzącą po krawędziach tej bryły, która za wiera ka żdy jej wierzchołek dokładnie je -
den ra z (pa trz rys . 6). Taką drogę na zywamy cykle m Hamiltona , a graf zawierający taki cykl – grafem Hamil-
tona .

Problem Cyklu Hamiltona
Da ne:

Dowolny G.

Wynik: Znale źć cykl Hamiltona w grafie G albo s twierdzić, że takiego cyklu nie ma w grafie G.

Rysunek 6.
Dwuna s toś cian foremny i jego graf z za znaczonym cyklem Hamiltona

Różnica mię dzy problemami Eulera i Hamiltona tkwi w tym, że w pierws zym przypadku pos zukujemy cyklu za-
wierającego ws zys tkie połączenia , ka żde dokładnie ra z, a w drugim – cyklu zawierającego ws zystkie wierz-
chołki, również ka żdy dokładnie ra z. Różnica wydaje s ię być nie wielka, jednak obliczeniowo te dwa problemy
należą do diametralnie różnych kla s złożonoś ci. Problem Eulera ma ła twe rozwiązanie – wys tarczy sprawdzić,
czy stopnie ws zys tkich wierzchołków s ą parzys te i czy graf jes t s pójny (tzn. jes t w „jednym kawa łku”). Nato-
mias t dla problemu Ha miltona nie podano dotychcza s efektywnego algorytmu rozwiązywania. Dalej w tym
punkcie zajmiemy się nas tępującą, praktyczną wersją problemu Hamiltona .

Problem komiwoja że ra (TSP)
Da ne:

n mia s t (punktów) i odległości między ka żdą parą mias t.

Wyniki: Tras a zamknięta , przechodząca przez ka żde mia s to dokładnie jeden ra z, której długoś ć je st możli-

wie najmniejs za .

Przykładem za stos owania problemu komiwoja żera (TSP – Tra velling Salesman Problem) może być zadanie
wyznaczenia najkróts zej tras y obja zdu prezydenta kra ju po wszys tkich s tolicach województw (s tanów –
w Stanach zjednoczonych, landów – w Niemcze ch itp.). Na tej tra sie, pre zydent wyjeżdża ze s tolicy kraju, ma
odwiedzić s tolicę ka żdego woje wództwa dokładnie jeden raz i wrócić do s tolicy kra ju.

Na rysunku 7 prze ds tawiliśmy jedną z możliwych tra s dla s tolic województw, a le nie jes te śmy pewni, czy jes t
ona najkrótsza . Obsługa biura prezydenta może je dnak chcie ć zna leźć najkróts zą tra s ę. W tym celu pos tano-
wiono generować ws zys tkie możliwe tra s y – za s tanówmy s ię, ile ich jes t. To ła two policzyć. Z Wars zawy moż-
na się udać do jednego z 15 mias t wojewódzkich. Będąc w pierwszym wybranym mieś cie, do wyboru ma my

> Znajdowanie najkrótszych dróg oraz najniższych i najkrótszych drzew

< 9 >

jedno z 14 mia s t. Po wybraniu drugie go mia s ta na tras ie, kolejne mias to można wybrać s poś ród 13 mia st i tak
dalej. Gdy osiągamy os tatnie mias to, to czeka na s tylko powrót do Wars zawy. A zatem ws zys tkich możliwych
wyborów jes t: 15*14*13*…*2*1. Oznaczmy tę liczbę na s tępująco:

15! = 15*14*13*…*2*1

a ogólnie

n! = n*(n – 1)*(n – 2)*…*2*1

Oznaczenie n! czytamy „n silnia”, a za tem n! jes t iloczynem kolejnych liczb ca łkowitych, od jeden do n. War-
tości tej funkcji dla kolejnych n ros ną bardzo s zybko, patrz tabela 1.

Tabela 1.
Wartości funkcji n!

n

n!

10

3628800

15

1.30767*10

12

20

2.4329*10

18

25

1.55112*10

25

30

2.65253*10

32

40

8.15915*10

47

48

1.24139*10

61

100

9.3326*10

157

Z wartości umies zczonych w tabeli 1 wynika , że pos ługując się superkomputerem o mocy 1 PFlops, czyli wy-
konującym 10

15

operacji na s ekundę , w realizacji na szkicowanej metody, służącej do znale zienia najkróts zej

tra s y dla prezydenta, otrzymanie takiej tra s y w przypadku Polski zabrałoby mniej niż s ekundę. Jednak w ol-
brzymim kłopocie znajdzie się pre zydent Stanów Zjednoczonych chcąc taką s amą metodą znaleźć najkrót-
s zą tra s ę objazdu po s tolica ch ws zys tkich kontynentalnych s tanów (jes t ich 49, z wyjątkiem Hawa jów) trwa-
łoby to 3.9*10

38

lat.

Znane są metody rozwią zywania problemu komiwoja żera szybsze niż na s zkicowana powyżej, je dnak

problem TSP pozos taje bardzo trudny. W takich przypadkach częs to s ą s tosowane metody, które s łużą do
s zybkie go znajdowania rozwią zań przybliżonych, nie koniecznie najkróts zych. Jedna z takich metod, zwa -

Rysunek 7.
Przykładowa tras a przejazdu prezydenta po s tolicach woje wództw

< 10 >

Informatyka +

na metodą najbliżs zego s ą siada , polega na przeje żdżaniu w ka żdym kroku do mia s ta , które znajduje się naj-
bliżej mia sta , w którym s ię znajdujemy – jes t to typowe podejś cie zachłanne, gdyż na ka żdym kroku chcemy
wykonywa ć możliwie na jleps zy ruch. W rozwią zaniu na sze go problemu tą metodą , pierws zym odwie dzonym
mias tem powinna być Łódź, później Kielce, Kraków, Ka towice , … Nies tety, tra sa otrzymana metodą najbliżs ze -
go s ą siada nie jes t króts za niż tras a na szkicowana na rys. 7.

W tym rozdziale przeds tawimy wybrane za s tosowania grafów w informa tyce. Głównie tymi grafami będą
drze wa. Drzewo jes t grafem, który nie zawiera cyklu, czyli drogi zamkniętej, i je st s pójny, czyli jes t w „jednym
kawałku”. Ze spójnoś ci wynika , że ka żde dwa wierzchołki w drze wie są połączone drogą , a z braku cyklu – że
dla ka żdych dwóch wierzchołków is tnieje dokładnie jedna droga, która je łączy. Na ogół w zas tos owaniach
informa tycznych drzew, drzewa mają wyróżniony wierzchołek, który na zywamy korzeniem. Na rysunku 8 s ą
prze ds tawione przykładowe drze wa.

Rysunek 8.
Przykładowe drze wa

W tym rozdziale przeds tawimy trzy pros te zas tos owania drzew. W punkcie 3.1.omówimy krótko reprezento-
wanie wyra żeń na drzewie. Nas tępnie wykorzys tamy drzewa do repre zentowania algorytmów (punkt 3.2) i na
końcu (punkt 3.3) na s zkicujemy metodę tworzenia krótkich kodów.

Na początku nauki matema tyki w s zkole pods tawowej s potkaliś cie się z drzewem jako s chematem obliczania
wartoś ci wyra żenia . W takim drze wie, zwanym drzewem wyra żenia , argumenty wyra żenia (liczby lub zmien-
ne) znajdują się w wierzchołkach końcowych (zwanych wis zącymi a także liś ćmi), a dzia łania są umies zczo-
ne w wierzchołkach pośrednich. Przykłady takich drze w są poka zane na rys . 9. Wyróżniony wierzchołek drze -
wa na zywa się korzeniem. W teks tach informatycznych, drzewo jes t na ogół rys owane z korzeniem u góry, jak
po prawej s tronie rysunku. Do elementów drzewa częs to s tos uje s ię na zewnictwo wzięte z dendrologii – ko-
rzeń, liście.

wie rzchołki
końcowe – liś cie

wie rzchołki
końcowe – liś cie

korzeń

korzeń

6

+

–

–

+

( )

2

( )

2

/

x

y

a

b

13

13

5

3

4

*

*

wie rzchołki
pośrednie

Rysunek 9.
Drzewa wyrażeń: (6 + 3)*(5 – 3*4) i (x

2

+ y

2

)/ (a – b)

> Znajdowanie najkrótszych dróg oraz najniższych i najkrótszych drzew < 11 >

Wykonanie obliczeń za pis anych w pos taci drze wa wyra żenia polega na „zwinięciu” te go drze wa, począw-
s zy od liś ci, czyli przejś ciu od liś ci do korzenia, w którym jes t otrzymywa na wartoś ć wyra żenia . Stosujemy
przy tym oczywis tą za s adę: aby móc wykonać dane działanie (umies zczone w wierzchołku pośrednim) musi-
my znać jego argumenty. A zatem, w wyra żeniu po lewej s tronie na rys . 9. nie można wykonać odejmowania,
zanim nie będzie znana wartoś ć odjemnika w wierzchołku powyżej, czyli na jpierw nale ży wykonać mnożenie
umies zczone w tym wierzchołku. Proponujemy prześ ledzenie kolejnoś ci wykonania działań podczas oblicza -
nia wartości wyra żeń repre zentowanych przez drzewa na rys . 9.

Drze wa wyra żenia s ą przydatne przy interpretacji i tworzeniu pos taci wyra żenia w tak zwanej odwrotnej nota -
cji pols kiej (ONP), w której zbę dne s ą nawias y. Na zwa tej notacji pochodzi od twórcy notacji polskiej, polskie -
go logika Jana Łuka siewicza (1878-1956). Ta notacja jes t s tos owana w wielu językach programowania , była
wykorzys tana również w kalkulatorach He wlett-Packard i Sinclair. Pos tać ONP wyra żenia tworzy się s tosując
rekurencyjnie na s tępującą za s adę: Zacznij w korzeniu i wypisz to, co jes t w wierzchołku dopiero po wypis a -
niu tego co jes t w lewym poddrze wie a później tego, co jes t w prawym poddrzewie. Dla przykładu, za s tosuj-
my tę za sadę do drzewa po le wej s tronie na rys. 9. Przed wypis aniem znaku mnożenia musimy najpierw wypi-
s ać to, co jes t w le wym poddrzewie i w prawym poddrzewie. Przechodzimy więc do lewego poddrzewa i s to-
sujemy w nim tę samą za sadę: aby wypis ać znak dodawania najpierw wypisujemy oba argumenty tego dzia -
ła nia, czyli dla lewego poddrze wa wyra żenia ma pos tać 6 13 +. Podobnie , dla prawego poddrzewa otrzymuje -
my 5 3 4 * – . A zatem ca łe wyra żenia ma na s tępującą pos tać ONP: 6 13 + 5 3 4 * – *.

Drzewo algorytmu jes t jednym ze sposobów zapis ywania algorytmów, przypominającym schematy blokowe.
Na rysunku 10 jes t przeds tawione drze wo algorytmu porządkowania trzech liczb a, b, c.

Rysunek 10.
Drze wo porządkowania trze ch liczb

Wierzchołki końcowe drzewa algorytmu zawierają ws zys tkie możliwe rozwią zania – w nas zym przykładzie
s ą to wszys tkie możliwe uporządkowania trze ch elementów. Takich uporządkowa ń jes t 6, a wykonywanie al-
gorytmu zapisa nego w pos taci drzewa , rozpoczyna s ię w korzeniu te go drze wa. Dzieje s ię zatem nieco ina -
czej niż w drzewie wyra żenia . Zapis anie tego a lgorytmu w postaci drzewa jes t przejrzys tym opis em wykony-
wanych operacji i ich kolejności. Ponadto drzewo algorytmu może służyć do kons truowania i analizowania al-
gorytmów.

Drze wo na rysunku 10 może być łatwo rozszerzone do drze wa a lgorytmu, który służy do porządkowa-

nia czterech liczb a , b, c i d. Wystarczy w tym celu wstawić czwarty element d do uporządkowanych ciągów
trzech pierws zych elementów – w tym celu należy wykonać dwa dodatkowe porównania zaczyna jąc od środ-
kowe go elementu.

Drze wo algorytmu może s łużyć do okre ślenia liczby operacji wykonywanych przez algorytm. Zilus trujemy
to na przykładzie drzewa prze ds tawionego na rysunku 10. Dla uzyskania konkretnego wyniku tego algoryt-
mu, który znajduje się w wierzchołku wis zącym tego drzewa , liczba wykonanych porównań równa s ię liczbie
wierzchołków pośre dnich na drodze od korzenia (licząc również korzeń) do te go wierzchołka – tę liczbę na -
zywamy długoś cią takiej drogi. Na przykład, jeśli dane trzy liczby a, b i c spełniają nierówności c ≤ a ≤ b lub
c ≤ b ≤ a , to algorytm wykonuje 2 porównania , a w pozos tałych przypadkach – wykonuje 3 porównania . Naj-

< 12 >

Informatyka +

większa długoś ć drogi z korzenia do wierzchołka końcowego w drzewie na zywa się wys okoś cią drzewa . Drze -
wo na rysunku 10 ma wysokość 3. Wysokość drzewa to najwięks za liczba opera cji wykonywanych w algoryt-
mie dla jakiegokolwiek układu danych. W algorytmice wielkoś ć ta na zywa się złożonością obliczeniową algo-
rytmu. Jak ilustruje to na sz przykład, je st to złożoność pe s ymist yczna lub złożonoś ć najgorszego przypad-
ku, gdyż w niektórych przypadkach algorytm może działać s zybciej. Dla danego problemu mamy tym lepszy
(s zybs zy) algorytm, im mniejs zą wysokość ma jego drzewo.

Drze wo a lgorytmu może być wykorzys tane do wyka zania , ile operacji mus i wykona ć ja kikolwiek algorytm
rozwią zywa nia dane go problemu, co może być wykorzys ta ne przy dowodzeniu opt ymalnoś ci a lgorytmów,
patrz [5].

Pojemnoś ć pamięci komputerów roś nie w je s zcze więks zym tempie niż s zybkoś ć proces orów. Możliwoś ć za -
pis ania w pamię ci komputera ca łej ks ią żki spowodowa ła chęć zapis ania ca łych bibliote k. Możliwoś ć poka -
zania na ekra nie monitora dobre j ja koś ci obra zu rozwinę ła s ię do rozmiarów całe go filmu. Alterna tywą dla
powięks zenia pamię ci jes t kompres ja danych, czyli minimalizowanie ich objętoś ci przez reprezentowanie
w zwięzłej pos taci. Gwa łtowny rozwój metod i form komunikowania s ię nie byłby możliwy bez cią głego ulep-
s zania metod kompres ji danych. Odnosi się to zarówno do tra dycyjnych form wymiany informa cji, takich ja k:
faks , modem czy tele fonia komórkowa , jak i do wymiany informacji za poś rednictwe m sie ci Internet, w t ym
zwła s zcza do wymiany informa cji multime dialnych. Kompresja da nych jes t możliwa dzięki wykorzys taniu
pewnych włas noś ci danych, na przykład częs to powtarzające się fragmenty można za s tę pować umownym
s ymbolem lub im częś ciej jakiś fra gment wys tępuje tym mniejs za (króts za) powinna być jego re pre zenta -
cja. W dals zej częś ci te go punktu zajmie my się je dynie kompresją teks tu, która polega na odpowie dnim ko-
dowa niu znaków.

Trudno uwierzyć, ale his toria kompre sji informacji ma s wój początek … w połowie XIX wieku. 24 maja 1844
roku Samuel Mors e po ra z pierws zy posłużył się zbudowanym przez siebie tele grafem i przesłał na odległoś ć
37 mil (z Kapitolu w Wa s zyngtonie do Baltimore) depes zę , w której zacytował Biblię „To, co uczynił Bóg” (ang.
What Hath God Wrought!). Jego osiągnięciem było nie tylko zbudowanie telegrafu, ale równie ż opracowanie
specjalnego alfabetu, zwane go alfabetem Morse’a , umożliwiającego kodowanie znaków w tekś cie za pomocą
dwóch s ymboli – kropki i kreski, którym wtedy odpowiadały krótsze lub dłuższe impuls y elektryczne, a dzi-
siaj mogłyby to być cyfry 0 i 1. Mors e przy konstrukcji s wojego alfabetu przyją ł założenie, że im częś ciej znak
wys tępuje w informacji, tym krótszy powinien mieć kod. Dla tego w jego alfabecie litera E ma kod (kropka),
a litera T ma kod – (kreska), gdyż s ą to najczęś ciej wys tępujące litery w tekstach języka angielskie go. W ję zy-
ku pols kim byłyby to odpowie dnio litery A oraz I. Wadą alfabe tu Morse’a je st koniecznoś ć s tosowania znaku
oddzielającego litery, gdyż kod danej litery może być początkową częś cią kodu innej litery. Na przykład zapis

może oznaczać dwie litery EE a także literę I, która ma taki kod.

Zauwa żmy, że s tos ując kod ASCII ws zys tkie znaki s ą kodowane za pomocą jednakowej liczby bitów.

Prze ds tawimy tera krótko kod Huffmana , który je st zbudowany na podobnych za sadach co alfabet Morse’a ,
ale nie ma wspomnianej wady tego alfabetu, czyli nie muszą być s tos owane zna ki do rozdzielania kodów li-
ter teks tu. W kodzie Huffmana:

■

znaki s ą zapis ywane również za pomocą dwóch znaków (cyfr 0 i 1);

■

kod żadnego znaku nie jes t początkiem kodu żadnego innego znaku – nie trzeba więc s tosować znaków
rozdzielających;

■

śre dnia długoś ć kodu znaku w tekście jes t możliwie najmniejs za .

Kod Huffmana tworzy się za pomocą specjalnego drzewa, drze wa Huffmana , w którym powyżs ze wła sności
są realizowane w na stę pujący sposób:

■

na ga łę ziach drzewa są umieszczone cyfry 0 i 1;

■

znaki, dla których jes t tworzony kod, znajdują się w wierzchołkach wis zących drzewa;

■

wierzchołki wis zące ze zna kami o więks zej częs tości występowania w teks tach znajdują się wyżej niż
wierzchołki ze znaki o mniejszych częs toś ciach.

> Znajdowanie najkrótszych dróg oraz najniższych i najkrótszych drzew < 13 >

Drze wo Hoffmana dla da nego zes tawu znaków o poda nych czę stotliwoś ciach jes t budowane sukces ywnie
przez łączenie ze s obą na każdym e tapie dwóch poddrze w o najmniejs zych częs totliwoś ciach i zas tępowaniu
ich poddrzewem o sumie ich częs totliwości. Szczegółowy opis algorytmu Huffmana można znaleźć w pod-
ręczniku [2] i w ksią żce [6]. Na rys unku 11 przeds tawiamy drzewo Huffmana otrzymane tą me todą dla na s tę -
pujących znaków i ich częs totliwości (to s ą rzeczywiste częs totliwości wys tępowania tych liter w teks tach
w ję zyku polskim):

a

8.71

b

1.29

d

3.45

k

3.10

o

7.90

r

4.63

W pierwszym kroku tworzenia tego drze wa zgodnie z na s zkicowanym algorytmem, łączone s ą dwie najmniej-
s ze częs totliwoś ci odpowiada jące literom b oraz k i za stępowane są przez czę s totliwoś ć 1.29 + 3.10 = 4.39.
Nas tępnie jes t łączona częs totliwoś ć 3.35 (litera d) z otrzymaną przed chwilą częs totliwością , itd.

0

0

0

0

1

1

1

a

o

d

b

k

r

1

1

0

Rysunek 11.
Drze wo Huffmana dla s ześ ciu liter

Na pods tawie drzewa z rysunku 11 otrzymujemy na s tępujące kody liter:

a

00

b

1010

d

100

k

1011

o

01

r

11

Słowo ABRAKADABRA ma w otrzymanym kodzie pos tać 00101011001011001000010101100, złożoną z 29
cyfr, a s tosując kod ASCII – pos tać tego słowa miałaby długość 88 znaków. Odpowiada to kompresji o wiel-
koś ci 60%.

Algorytm Huffmana je st wykorzys tywany w wielu profe sjonalnych metodach kompre sji teks tu, obra zów
i dźwięków, równie ż w połączeniu z innymi me todami. Redukcja wielkoś ci danych przy s tos owaniu tego al-
gorytmu wynosi około 50% (w przypadku obra zów i dźwięków kodowane s ą nie s ame znaki, ale różnice mię -
dzy kolejnymi znakami).

W tej czę ści wykładu przeds ta wiamy algorytmy na grafach, które mają wiele za s tos owań pra ktycznych, s ą
jednocze śnie ilus tracją typowych sposobów rozwią zywania problemów definiowanych na grafach. Szczegó-
łowe rozwa ża nia dotyczące prze ds tawionych tutaj algorytmów można znale źć w ksią żce [7].

< 14 >

Informatyka +

W cza sie wykładu, działanie pre zentowanych algorytmów będzie ilus trowane za pomocą specjalne go progra-
mu edukacyjnego Algorytmy Grafowe, w którym można:

■

budować i modyfikować grafy,

■

zapoznać się z pods ta wowymi s posobami reprezentowa nia grafów w komputerze,

■

śledzić przebieg działania pods tawowych algorytmów grafowych, w tym m.in. zwią zanych
z przes zukiwaniem grafów, znajdowaniem najkrótszych dróg w grafach i znajdowaniem najkróts zego drzewa
rozpinającego grafu; podczas działania algorytmu, jego przebie g jes t zs ynchronizowany z demons tracją
wykonywania programu w pseudo-ję zyku programowania , poka zywane s ą również zmieniające s ię s tany
s truktur danych, wykorzys tywanych w algorytmach.

Na rysunku 12 jest prze ds tawione okno programy Algorytmy Grafowe , w którym wida ć graf i jego kompute -
rowe reprezentacje.

Rysunek 12.
Okno w programie Algorytmy Grafowe z grafem dwuna s tościanu i je go komputerowymi repre zentacjami

W dals zej częś ci tego rozdziału, najpierw definiujemy grafy i omawia my ich komputerowe reprezentacje. Na-
s tę pnie przeds tawiamy dwie grupy problemów definiowa nych na grafach i demons trujemy dzia łanie wybra-
nych algorytmów ich rozwią zywania .

Jak już pis aliśmy, ka żdy gra f składa się ze zbioru wierzchołków i zbioru połączeń. Wyróżniamy dwa rodzaje
gra fów: nieskierowane i skierowane.

Grafy nie skierowane na zywamy po pros tu grafami. Ws zys tkie połączenia w nich s ą nieskierowane , a to

oznacza, że mogą być przechodzone w obie s trony. Połączenia w grafach nieskierowanych na zywamy krawę -
dziami. Przykładowy gra f jes t poka zany w oknie programu na rys unku 12.

Z kolei, grafy skierowane nazywamy digrafami. Ws zys tkie w nich połączenia mają za znaczony kierunek

przechodzenia . Połączenia w digrafach na zywamy łukami. Przykładowy digraf jes t poka zany na rysunku 13.

Grafy i digrafy można repre zentować w komputerze na wiele sposobów. Na począ tku przyjmijmy, że wierz-
chołki s ą ponumerowane kolejnymi liczbami 1, 2, 3, … W ka żdym ze sposobów reprezentowania digra fów

> Znajdowanie najkrótszych dróg oraz najniższych i najkrótszych drzew < 15 >

i grafów w komputerze jes t zapis ywane s ą sie dztwo wierzchołków, czyli dla ka żdego wierzchołka je st po-
dane, z którymi innymi wierzchołkami jes t on połączony. W przypadku grafów s ymetrycznych, dla ka żdego
wierzchołka podajemy numery wierzchołków, z którymi jes t on połączony, a dla digrafów – podajemy nume -
ry wierzchołków, do których prowadzi skierowane połączenie.

Najpopularniejs ze s ą dwie reprezentacje: macierzowa i w pos taci lis t są siadów. W reprezentacji macierzowej,
jeś li graf za wiera połączenie z wierzchołka j do wierzchołka k, to w macierzy s ą siedztwa na przecięciu wier-
s za j z kolumną k jes t 1, a w przeciwnym ra zie jes t 0. Z kolei w lis tach s ąs iedztwa, w liś cie o numerze j wys tę -
pują ws zys tkie wierzchołki, które są s ą siednie do wierzchołka k. Na rysunkach 12 i 13 ilustrujemy te kompu-
terowe reprezentacje dla grafów przeds tawionych na tych rysunkach. Są siedztwo w grafach należy traktować
jako relację s ymetryczną , natomias t w digrafach są sie dztwo jes t wska zywany przez zwrot łuków.

Rysunek 13.
Digraf i jego komputerowe repre zentacje

Drogą w grafie na zywamy ciąg wierzchołków, dla których graf zawiera połą czenia między kolejnymi wierz-
chołkami te go cią gu. Za uwa żmy na rysunkach 12 i 13, że połączenia mają przypisane im liczby – s ą to wagi
połączeń, które mogą oznaczać na przykład rzeczywistą długoś ć połączenia . Długoś ć drogi definiujemy jako
sumę długości połączeń, które tworzą tę drogę. Na przykład, droga (2, 3, 8, 13, 9, 4) w grafie na rysunku 12 ma
długoś ć 9+5+8+1+9 = 32, a droga (1, 3, 4, 5, 2) w digrafie na rys unku 13 ma długoś ć 5+5+1+4 = 15.

Is tnieje wiele różnych problemów, w których celem jes t znalezienie najkróts zej drogi. Jeden z takich

problemów był przedmiotem nas zych rozwa żań w punkcie 2.3, gdzie zas tanawialiś my się, jak zna leźć tra sę
dla komiwoja żera , czyli najkróts zy cykl przechodzący przez ka żdy wierzchołek w grafie dokładnie jeden ra z.
Kla s yczne problemy najkrótszych dróg można podzielić na nas tępujące grupy:

1. zna leźć najkróts zą drogę mię dzy wybraną parą wierzchołków w grafie;
2. znaleźć najkrótsze drogi z wybranego wierzchołka w grafie do wszystkich pozos tałych wierzchołków w grafie;
3. zna leźć najkróts ze drogi między ka żdą parą wierzchołków w grafie.

W tych s formułowania ch problemów, „znaleźć najkróts zą drogę” oznacza znaleźć długoś ć najkrótszej drogi
ora z cią g wierzchołków drogi o najkrótszej długości.

Łatwo zauwa żyć, że rozwią zanie problemu typu 1 może być wykorzys tane w rozwiązaniu problemów typu 2
i 3. Podobnie, rozwią zanie problemu typu 2 może być wykorzys tane do rozwią zania problemu typu 3. Na ogół,
rozwią zywanie problemu typu 2 może być przerwane, gdy mamy już rozwiązanie problemu typu 1. Dlatego za -
trzymamy s ię jedynie nad problemem typu 2 i dodatkowo założymy, że ws zystkie wagi połączeń s ą nieujem-
ne (w ogólnoś ci nie muszą być). A zatem, rozwa żymy na s tępujący problem, przyjmując dodatkowo, że s zuka-
my najkróts zych dróg w obcią żonych digrafa ch. Je śli chcemy znaleźć najkróts ze drogi w obcią żonym grafie s y-
metrycznym, to ka żdą krawędź traktujemy jako parę łuków prze ciwnie skierowanych.

< 16 >

Informatyka +

Problem najkróts zych dróg z ustalonego wierzchołka w digrafie obcią żonym
Da ne:

digraf G z łukami obcią żonymi nieujemnymi wagami; wybrany wierzchołek s.

Wynik: najkróts ze drogi w G z s do ws zys tkich pozos tałych wierzchołków w digrafie G.

Do rozwią zania tego problemu posłużymy się algorytmem Dijks try. Nie zamie szczamy tutaj jednak s zczegó-
łowego opisu tego algorytmu, tylko opiszemy jego główną ideę, a nas tępnie w cza sie wykładu zilus trujemy
dzia łanie tego algorytmu posługując s ię programem Algorytmy Grafowe , patrz rysunek 14.

Algorytm Dijks try ma charakter me tody za chłannej. Startujemy z dane go wierzchołka s, zaliczamy go

do rozwią zania i w pierws zym kroku obliczamy długoś ci dróg z s do ws zys tkich jego wierzchołów s ą siednich
(te drogi składają s ię z pojedynczych łuków) a nas tępnie wybieramy wierzchołek s ąsie dni w, który jes t najbli-
żej s – wierzchołek w zalicza my do rozwią zania i dla ka żde go wierzchołka v, który nie należy jes zcze do roz-
wią za nia, s pra wdzamy, czy droga z s do v przez w nie jes t króts za od dotychczas owej drogi na jkróts zej z s
do v. Jeśli tak jes t, to poprawia my długości dróg. Na s tępnie , ponownie wybieramy wierzchołek spośród tych,
które nie należą jes zcze do rozwią zania , a który jes t najbliżs zy s i powtarzamy to postę powanie. Liczba ite -
racji w tej metodzie wynosi n – 1, bo tyle wierzchołków trzeba dołączyć do rozwią zania w kolejnych krokach.

Polecamy prze śledzić dzia łania algorytmu Dijks try w programie Algorytmy Grafowe na wybranych

przykładach digrafów i grafów.

Rysunek 14.
Demonstracja działania algorytmu Dijkstry w programie Algorytm Grafowe, zastosowana do digrafu z rysunku 13

Jak pamiętamy, drzewo jes t grafem, który je st s pójny i nie za wiera cykli, a graf jes t spójny, je śli ka żda para
jego wierzchołków jes t połą czona drogą. Zakładamy tutaj że graf jes t s yme tryczny. Jeśli graf jes t spójny, to
można znaleźć w nim podgraf, który jes t drzewem – takie drze wo w grafie na zywamy drzewem rozpinającym.
Drzewo rozpinające w grafie spójnym można znajdować na dwa spos oby. Drzewo o n wierzchołka ch ma do-
kładnie n – 1 krawędzi:

1. usuwać krawę dzie , które nie powodują rozpojenia grafu, tak długo jak długo graf ma więcej niż n – 1 krawę -

dzi, gdzie n jes t liczbą wierzchołków w grafie;

2. wybierać krawę dzie w grafie, ale tylko takie , które nie powodują pows tania cyklu wśród wybranych krawę -

dzi; postępować tak długo, a ż wybranych zos tanie n – 1 kra wę dzi, gdzie n jes t liczba wierzchołków w grafie.

> Znajdowanie najkrótszych dróg oraz najniższych i najkrótszych drzew < 17 >

Rozwa żany przez nas problem ma na s tępującą pos tać:

Problem najkróts zego drzew rozpinającego w grafie obcią żonym
Dane:

graf G z krawędziami obcią żonymi wagami.

Wynik: najkróts ze drzewo rozpinające w grafie G. Za długość drzewa przyjmujemy sumę wag (długoś ci) jego

kra wę dzi.

Najbardziej znanym algorytmem rozwią zywania tego problemu jes t zachłanny algorytm Kruskala . Polega on
tworzeniu drzewa rozpinającego metodą nr 2 przy za łożeniu, że krawędzie s ą rozpatrywane w kolejnoś ci od
najlżejszych (najkróts zych) Opis zemy ten algorytm w pseudo-języku programowania . Zakładamy, ze rozwa -
żany graf jes t spójny.

algorytm Kruskala;

begin

T:=pusty; {T – zbiór kraw

ę dzi tworzonego drzewa}

E – zbiór kraw

ę dzi grafu G;

while T ma mniej elementów ni

ż n – 1 do begin

wybierz najkrótsz

ą krawę dź e w zbiorze E;

usu

ń e z E;

if e nie tworzy cyklu z kraw

ę dziami w T then

do

ł ą cz krawę dź e do zbioru T

end

end

Na rysunku 15 jes t przeds tawione okno z demons tracją algorytmu Kruskala na los owym grafie.

Ciekawą modyfikacją algorytmu Krus kala je st algorytm Prima-Dijks try, który jes t również algorytmem za-
chłannym, ale podobnie jak algorytm Dijks try dla znajdowania najkróts zych dróg, może rozpocząć budowa -
nie najkróts zego drzewa rozpinającego zaczynając w dowolnym wierzchołku grafu, jako korzeniu. Proponuje -
my prześle dzić dzia łanie tego algorytmu w programie Algorytmy Grafowe .

Rysunek 15.
Demons tracja działania algorytmu Kruskala w programie Algorytm Gra fowe

< 18 >

Informatyka +

1. Cormen T.H., Leisers on C.E., Rive st R.L., Wprowadzenie do algorytmów, WNT, Wars zawa 1997
2. Gurbiel E., Hard-Olejniczak G., Kołczyk E., Krupicka H., Sysło M.M., Informatyka , Część 1 i 2, Podręcznik dla

LO, WSiP, Warsza wa 2002-2003

3. Harel D., Algorytmika. Rzecz o istocie informatyki, WNT, Wars zawa 1992
4. Knuth D.E., Sztuka programowa nia, Tomy 1 – 3, WNT, Wars zawa 2003
5. Sys ło M.M., Algorytmy, WSiP, Wa rszawa 1997
6. Sys ło M.M., Piramidy, szys zki i inne konstrukcje algorytmiczne, WSiP, Wars zawa 1998. Kolejne rozdziały tej

ks ią żki s ą zamies zczone na stronie: http:// www.wsipnet.pl/ kluby/ informatyka _eks tra .php?k= 69

7. Sys ło M.M., Deo N., Kowalik J.S., Algorytmy optymalizacji dyskretnej z programami w języku Pascal, WN PWN,

Wars zawa 1997

8. Wilson R.J., Wprowadzenie do teorii grafów, WN PWN, Wars zawa 1998

Notatki

< 19 >

W projekcie

, poza wykładami i warsztatami,

przewidziano następujące działania:

■

24-godzinne kursy dla uczniów w ramach modułów tematycznych

■

24-godzinne kursy metodyczne dla nauczycieli, przygotowujące

do pracy z uczniem zdolnym

■

nagrania 60 wykładów informatycznych, prowadzonych

przez wybitnych specjalistów i nauczycieli akademickich

■

konkurs y dla uczniów, trzy w ciągu roku

■

udział uczniów w pracach kół naukowych

■

udział uczniów w konferencjach naukowych

■

obozy wypoczynkowo-naukowe.

Szczegółowe informacje znajdują się na stronie projektu