FAKULTET ZA INFORMACIONE TEHNOLOGIJE I INŽENJERSTVO
OSNOVNE STUDIJE SMER INFORMACIONI SISTEMI
Predmet:
Diskretna matematika
Grafovski algoritmi
Profesor:
Student:
dr. Predrag Kovačević
Aleksa Đurišić M0059/18
Grupa 1
Beograd, decembar 2019.
Sadržaj:
1.Razvoj i značaj teorije grafova ............................................................................... 1
2. Grafovi-osnovni pojmovi ...................................................................................... 2
3. Grafovsko „stablo“ ................................................................................................. 4
4. Obilazak grafa po širini (BFS) ............................................................................ 5
5. Obilazak grafa po dubini(DFS) ........................................................................... 9
6. Optimizacioni algoritmi .................................................................................... 13
6.1 Dijkstrin algoritam .......................................................................................... 13
6.2 Primov algoritam ............................................................................................ 17
6.3 Kruskalov algoritam ...................................................................................... 18
7. Zadaci ................................................................................................................ 21
8. Spisak korišćene literature ................................................................................ 28
9. Spisak priloga .................................................................................................... 28
2
Tokom godina, ova teorema je dokazivana i opovrgnuta više puta, a na kraju je uspeo da je
dokaže računar posle više od 1200 sati rada. Ovaj problem, iako jednostavan, imao je velikog
uticaja na dalji razvoj matematik,e posebno kombinatorike i preciznije teorije grafova.
Danas, predstavljanje raznih problema u vidu modela, u kome se složeni objekat uprošćava i
definišu se proizvoljne nelinearne relacijama između njegovih delova, je najčešće prvi zadatak u
rešavanju problema. Za takva modeliranja se najčešće koriste grafovi. Operacije sa grafovima su
često veoma složene, pa se za njihovo rešavanje koriste računari. Da bi računar razumeo
problem, potrebno je napraviti algoritam, tj. definisati tačno određen broj koraka i njihov
redosled, koji dovodi do rešenja. Tako dolazimo do grafovskih algoritama, kojima se zadaju
načini obilaska i pretrage grafova, na način koji je razumljiv računaru.
2. Grafovi-osnovni pojmovi
Pre nego što krenemo da razmatramo same algoritme, neophodno je da se podsetimo nekih
osnovih pojmova vezanih za grafove.
Graf je apstraktni matematički objekat koji se sastoji od čvorova (odnosno tačaka) i grana
(odnosno linija) između tih tačaka. Čvorovi se u matematici, obeležavaju slovom V, a grane
slovom E.
Slika 3 Primer grafa
Dva
susedna čvora
su krajnje tačke svake grane. Na slici 3 susedni čvorovi su:
A i B, A i E, A i D itd., dok npr. čvorovi A i C nisu susedni.
Grana koja spaja čvor sa samim somom naziva se
petlja
. Na slici 3, petlja postoji u čvoru
F
.
Stepen čvora
je broj grana grafa koji imaju kraj u tom čvoru. Na slici 3 čvorovi B,C i G su
stepena 2, čvorovi A i D su stepena 3, čvor F je stepena 4 (ako u čvoru postoji petlja onda se ona
računa dva puta), a čvor E je stepena 5.
Put
je niz grana koje su međusobno povezane.
Prost ili elementaran put
je put kod koga se
kroz jedan čvor prolazi tačno jedan put. Na slici 3 jedan od mogućih prostih puteva je
A-B-C-D-E-F-G. Dužinu puta čini zbir svih grana.
Graf je
povezan
ako postoji bar jedan put od svakog čvora do bilo kojeg drugug čvora. Graf na
slici 3 je povezan.
3
Graf je
potpuni
ako ima granu između svaka dva čvora (vidi sliku 4).
Slika 4 Primer potpunog grafa
Ako je početni čvor ujedno i krajnji, takav put se naziva
ciklus, kontura ili petlja.
Na slici 4
imamo nekoliko zatvorenih ciklusa, npr. A-B-E-A, A-C-D-A itd.
Postoje neorijentisani i orijentisani grafovi
. Sve slike grafova do sada bile su slike
neorijentisanih grafova, tj. po npr. grani A-B (slika 4) smo mogli da pređemo od čvora Ado
čvora B, ali isto tako da pređemo od čvora B do čvora A.
Kod
orijentisanih (usmerenih) grafova
, ako je grana usmerena od čvora A do čvora B , nije
moguće tom granom preći od čvora B do čvora A. Orijentisani graf se označava kao na slici 5.
Slika 5 Primer orijentisanog (usmerenog) grafa
Postoje i mešoviti grafovi kada se graf sastoji od usmerenih i neusmerenih grana.
Na slici 5, čvor B je susedni čvoru A, ali ne važi i obrnuto, tj. čvor A nije susedan čvoru B.
Ukupan stepen nekog čvora čine sve grane koje u njega ulaze(ulazni stepen)i sve grane koje iz
njega izlaze (izlazni stepen). Čvor E na slici 5 ima ukupni stepen 3 (izlazni stepen 1 +ulazni
stepen 2). Kod petlje koja počinje i završava se u istom čvoru smer nije bitan.
Usmerenost grafa možemo posmatrati kao jednosmernu ulicu u gradu gde su čvorovi A i B npr
dve zgrade duž te ulice. Ovom ulicom stižemo od zgrade A do zgrade B, ali ne možemo da
stignemo od zgrade B do zgrade A.
Čvorovi u grafovima su običnona neki način označeni (imenima, slovima, brojevima).
Što se grana tiče, ukoliko svakoj grani
prisvojimo neku vrednost, tj. pored grane napišemo neki
broj, kažemo da grana ima određenu težinu i da se radi o težinskom grafu. Svi grafovi na slikama
3-5 su beztežinski.
Na slici 6 dat je primer težinskog, neusmerenog grafa.
5
4.
Obilazak grafa po širini (BFS)
Način obilaska čvorova u BFS algoritmu možemo da predstavimo ovako: zamislimo da
se od korenog, početnog čvora širi talas plamena. On prvo doseže do svih prvih susednih
čvorova koji imaju isti nivo udaljenosti od početnog čvora, zatim do njihovih susednih
čvorova i td. Redosled u kome se „zapale“ tj. posećuju čvorovi u tekućem nivou diktira
redosled paljenja, tj. posete čvorova - suseda u sledećem nivou. Jedna iteracija algoritma
odgovara širenju požara u širinu za jednan čvor.
Hajde da pogledamo kako BFS algoritam radi na jednom primeru.
Slika 7 Graf za ilustraciju obilaska u širinu
Za početni čvor obilaska uzećemo čvor
v
1 (nulti nivo). Njegova prva dva susedna čvora
su
v
2 i
v
3 (nivo 1) . Sledeći susedni čvora za
v
2 je čvor
v
4. Susedni čvor čvora
v
3 je
čvor
v
5 i
v
6. Čvorovi
v
4,
v
5 i
v
6 su na nivou 2. I poslednji u redosledu obilaska su
čvorovi
v
7 i
v
8 (sledeći susedi čvora
v
4) i čvor
v
9 (nivo 3).
Razapeto stablo ovog grafa pri pretrazi po širini dato je na slici 8
Slika 8 Razapeto stablo grafa sa slike7 za pretragu u širinu
Isprekidane linije predstavljaju veze između čvorova koje postoje u grafu ali nam za ovu
pretragu nisu značajne.
