Vladimir Balti
TEORIJA GRAFOVA
za studente Fakulteta organizacionih nauka
koji sluxaju Diskretne matematiqke strukture
B E O G R A D
2008
4
4. TEORIJA GRAFOVA
4. Teorija grafova
Kombinatorika (sa Teorijom grafova) je jedna od najstarijih oblasti matematike, ali i danas
je veoma aktuelna. Neki njeni problemi su zaokupljali matematiqare vekovima (poput problema
qetiri boje), dok su neke oblasti postale veoma aktuelne sa vrtoglavim razvojem raqunara i
njihovom sve veom primenom pri rexavanju matematiqkih problema.
Grafovi su matematiqki objekti koje veoma qesto sreemo u svakodnevnom ivotu. Ako pos-
matramo neku geografsku mapu sa mnoxtvom gradova koji su povezani nekim putevima – dobijamo
jedan graf. U skupu ljudi na nekom predavanju neki se meusobno poznaju, a neki ne – ako sve ljude
predstavimo taqkicama, a samo one koji se poznaju spojimo linijama dobiemo jedan graf, koji nam
daje dobru sliku poznanstva meu ljudima na tom predavanju. Strukturna formula nekog molekula
ili jedinjenja takoe predstavlja jedan graf. Xema nekog elektriqnog kola u teoriji kola ili
elektronici isto predstavlja jedan graf.
Grafovi nalaze primenu i u rexavanju tzv. problema za razbibrigu. Sada emo navesti neke
od njih:
•
Na slici su date 3 kue i 3 bunara. Povezati svaku kuu sa sva 3 bunara putevima, koji se
meusobno ne seku.
K
K
K
B
B
B
•
Odrediti najvei broj dama koje se mogu staviti na xahovsku tablu
n
×
n
tako da se one
meusobno ne napadaju.
•
Odrediti najmanji broj dama koje je potrebno postaviti na xahovsku tablu
n
×
n
tako da one
napadaju sva polja te table.
•
Koliko ima razliqitih postavljanja tih dama? (dva su postavljanja ista ako se mogu dobiti
okretanjem table – rotacijom ili simetrijom u odnosu na neku osu table)
•
Obii skakaqem xahovsku tablu
m
×
n
, tako da skakaq obie sva polja i da ni na jednom ne
bude vixe od jedan put.
•
Moe li se jednim potezom (bez dizanja olovke sa papira) nacrtati figura sa slike?
Iz ove grupacije je nastao i jedan od najpoznatijih grafovskih problema, a to je problem 4
boje.
Zbog velikog spektra primena, kao i izuzetno jednostavne veze definicije i osnovnih svojstava,
grafovi su oni naxli i veliku primenu ne samo u drugim matematiqkim oblastima poput kombi-
natorike, kombinatorne optimizacije, operacionih istraivanja, linearne algebre, kompleksne
analize, nego i u drugim (nematematiqkim) naukama kao xto su elektrotehnika, raqunarstvo, hemi-
ja, fizika, biologija, sociologija, vojne nauke...
Kroz naredna 2 primera ilustrovaemo primenu u raqunarstvu.
PRIMER 4.0.1.
Algoritam ranga stranice.
Najvea sopstvena vrednost grafa se naziva
spektralni radijus ili indeks grafa (kasnije emo se detaljnije upoznati sa ovim pojmom). Vektor
koji odgovara najveoj sopstvenoj vrednosti grafa (Peronov vektor) je baza za Algoritam ranga
stranice (eng.
PageRank algorithm
) koji koristi
Google
pri pretraivanju. Akademsko citiranje
radova se primenilo na Internet (
Web
), uglavnom kao prebrojavanje linkova koji vode do odeene
stranice. Ovo daje aproksimaciju o kvalitetu, odnosno vanosti neke stranice. Algoritam ranga
stranice produbljuje ovu ideju tako xto ne broji linkove od svih stranica podjednako, nego to
radi uz normalizaciju broja stranica koje polaze iz jednog qvora. Algoritam je razvijen na
Stenford Univerzitetu u Americi 1995. godine.
5
Pretpostavimo da na stranicu
A
ukazuju linkovi
T
1
, T
2
, . . . , T
n
i da je parametar
d
faktor otkaza
izmeu
0
i
1
. Broj
C
(
A
)
je broj linkova koji odlaze iz qvora
A
. Tada se rang za stranicu
A
raquna
kao:
P R
(
A
) = (1
−
d
) +
d
µ
P R
(
T
1
)
C
(
T
1
)
+
P R
(
T
2
)
C
(
T
2
)
+
. . .
+
P R
(
T
n
)
C
(
T
n
)
¶
.
Algoritam ranga stranice formira funkciju raspodele na skupu stranica, tako da je suma svih
rangova jednaka
1
. Vrednosti ranga stranica (to su
P R
) se mogu izraqunati prostim iterativnim
algoritmom i odgovaraju koordinatama u Peronovom vektoru matrice susedstva
Web
-a. Na nared-
noj slici su prikazane vrednosti ranga stranica za graf sa qetiri qvora. Napomenimo da moemo
izraqunati vrednosti ranga stranica za preko
26
miliona stranica za nekoliko sati na proseqnoj
radnoj stranici.
PRIMER 4.0.2.
Xirenje virusa u raqunarskim mreama.
Spektralna teorija grafova
ima lepe rezultate koji su usko povezani sa fiziqkim osobinama raqunarskih mrea. Nedavno je
dokazano da spektralni radijus grafa igra vanu ulogu u modeliranju xirenja virusa u mreama.
U
SIS
modelu (eng.
Susceptible - Infected - Susceptible
) svaki qvor u mrei je u jednom od dva stanja:
zaraen (moe da xiri virus) ili zdrav (osetljiv na virus). Ovaj model takoe pretpostavlja
istovremenu promenu stanja svih qvorova. Zato, qim se neki qvor zarazi postaje izvor zaraze,
odnosno qim se izleqi osetljiv je na ponovne infekcije. Epidemioloxka teorija predvia posto-
janje
epidemskog praga osetljivosti
(eng.
epidemic threshold
). Procenat infekcije po svakom linku
koji je povezan na zaraeni qvor je jednak
β
, dok je procenat leqenja za svaki zaraeni qvor
δ
.
Efektivna brzina xirenja virusa je prema tome definisana kao koliqnik
β/δ
. Epidemski prag os-
etljivosti
τ
je onda kritiqna vrednost za
β/δ
: za efektivnu brzinu xirenja virusa ispod
τ
virus
u mrei izumire; dok u sluqaju da je efektivna brzina xirenja virusa iznad
τ
virus preovlauje
- konstantan procenat qvorova ostaje zaraen u svakom trenutku.
Dokazano je u [11] da je
τ
=
1
ρ
(
G
)
, gde je
ρ
(
G
)
bax spektralni radijus matrice susedstva
A
grafa.
Dakle, xto je radijus manji, to je mrea otpornija na napade i xirenje virusa. Ovo prirodno
dovodi do postavljanja sledeeg problema:
Koji grafovi sa
n
qvorova imaju najmanji spektralni radijus?
Poznato je da put
P
n
ima najmanji spektralni radijus. Meutim u praksi, ovakvo rexenje nije
najoptimalnije jer bi sama komunikacija u mrei bila spora sa mogunoxu zaguxenja. Zato
postavljamo dodatne uslove, uzimajui u obzir razne invarijante grafova (dijametar, najvei
stepen, itd).
4.1. ISTORIJAT TEORIJE GRAFOVA
7
potrebno da pokae dovoljne uslove u opxtem sluqaju. Prvi potpuno korektan dokaz ovog
tvrenja je dao Hirholcer (nem.
Hierholzer
).
Na narednoj slici levo je predstavljena mapa Kenigsberga (iz vremena Ojlera) sa njegovim
mostovima. Ojler je svakoj obali i ostrvu pridruio qvorove grafa, a grane izmeu njih su
bili mostovi. Tako je on dobio jedan multigraf, koji je predstavljen na slici desno.
Ojler je qlanak o Problemu Kenigsbergxkih mostova napisao 1736. godine (i stoga se ta
godina uzima za osnivanje teorije grafova) i on je prvi put objavljen 1741. godine, ali je
tada probudio malo interesa meu ostalim matematiqarima. Neke stranice iz ovog rada su
prikazane na narednoj slici. Ovaj problem i rezultat su ostali malo poznati do kraja 19.
veka kada su ga engleski matematiqari or Lukas (eng.
George Lucas
, 1882.) i Raus Bol
(eng.
Rouse Ball
, 1892.) ukljuqili u svoje knjige o rekreativnoj matematici. Pojam Ojlerovog
grafa za graf koji se moe nacrtati ne podiui olovku sa papira se odomaio zahvaljujui
Kenigu, koji ga je iskoristio u svojoj pionirskoj knjizi o Teoriji grafova (1936. godine; vixe
o njoj kasnije).
Traenje Ojlerovog puta nalazi primenu u jox nekim problemima Kombinatorne optimizaci-
je, poput Problema kineskog poxtara (sa kojim emo se sresti kasnije), ali i u radu sa
laserima, gde nam je cilj da optimalno koristimo laser i samim tim pojeftinimo cenu fi-
nalnog proizvoda (metodama Kombinatorne optimizacije postignuta je uxteda vremena rada
i do 90%).
2.
Prvi znaqajniji rezultati Teorije grafova nakon Ojlerovih su stigli polovinom 19. veka.
Kirhofova teorema za matrice i stabla i Kejlijeva teorema (o njoj emo kasnije). Oba su
stigla direktno iz primena.
Fiziqar Kirhof je svoje tvrenje pokazao 1947. godine i ono mu je posluilo za izraqunavanje
jaqina elektriqnih struja u granama nekog elektriqnog kola (jer su nezavisni ciklusi u
potpunosti odreeni jednim razapinjuim stablom). Navedimo kako glasi ovo tvrenje.
Broj razapinjuih stabala
t
(
G
)
grafa
G
jednak je bilo kom kofaktoru Laplasove
matrice
L
.
Ova formulacija moda nije najjasnija, pa emo dati alternativnu formulaciju Kirhofova
teorema za matrice i stabla.
Za proizvoljne
s, t
∈ {
1
,
2
, . . . , n
}
broj razapinjuih stabala
t
(
G
)
grafa
G
jednak je
(
−
1)
s
+
t
puta determinanta matrice koja se dobija brisanjem vrste
s
i kolone
t
iz
matrice
L
(matrica
L
=
D
−
A
, gde je
A
matrica susedstva grafa
G
, a
D
je dijagonalna
matrica sa stepenima odgovarajuih qvorova, tj.
d
ii
=
d
(
v
i
)
i
d
ij
= 0
, za
i
6
=
j
).
