Predavanje 2

1.2. Izračunavanje stepena povezanosti mreže

• Pokazuje se da je u slučaju planarnih grafova ispunjena relacija: emax =3(v−2)

– Maksimalni broj grana u planarnom grafu emax predstavlja maksimalni broj grana kojima su direktno povezani čvorovi mreže, pri čemu se sve grane ukrštaju samo u čvorovima.

v = 3 e m ax = 3

v = 6 e m ax = 12

v = 4 e m ax = 6

v = 7 e m ax = 15

v = 5 e m ax = 9

v = 8 e m ax = 18

Figure1.14 Maksimalna povezanost planarnih grafova

1.2. Izračunavanje stepena povezanosti mreže

Figure1.15 Poredjenje stepena povezanosti dveju mreža

1.2. Izračunavanje stepena povezanosti mreže • I mreža Ga i mreža Gb imaju po 11 čvorova. • Maksimalni broj grana u ovim mrežama je jednak:

e max = 3 (v − 2) = 27 • Za mrežu koja sadrži v čvorova gama indeks se definiše kao odnos broja grana u mreži e i maksimalnog broja grana emax, tj:

1.2. Izračunavanje stepena povezanosti mreže γ=

e e max

e = 3 ( v −2)

• U slučaju mreža Ga i Gb, vrednosti indeksa respektivno iznose: 17 γa = = 0.63 27

10 γb = = 0.37 27

1.2. Izračunavanje stepena povezanosti mreže

• Vrednosti γ indeksa nalaze se u intervalu [0,1]. • U primeru koji smo razmatrali dobili smo da su za mreže Ga i Gb odgovarajuće vrednosti indeksa γa = 0.63 and γ = 0.37. b

Slika 1.15 Mreža G sa 11 čvorova i najmanjom mogućom vrednošcu gama indeksa

• Mreža G prikazana na slici 1.15 predstavlja drvo. • Pojedini parovi čvorova u mrezi G neće biti povezani u slučaju da uništimo jednu ili više grana. • Kada se mreži sa najmanjom vrednošću indeksa γ doda jedna ili više grana dolazi do stvaranja ciklusa. U ovom slučaju su pojedini parovi čvorova medjusobno povezani ne samo sa jednim putem.

• Jasno je da se sa dodavanjem većeg broja grana povećava i broj ciklusa, odnosno broj alternativnih puteva izmedju pojedinih parova čvorova.

Mreža sa jednim (a) i mreža sa dva (b) ciklusa

1.2. Izračunavanje stepena povezanosti mreže • Broj grana e u slučaju drveta koje sadrži v čvorova je jednak:

e=v−1 • Do stvaranja ciklusa dolazi kada je broj grana u mreži e veći od v ‑ 1.

1.2. Izračunavanje stepena povezanosti mreže

• Broj stvorenih fundamentalnih ciklusa u mreži dobija se kao razlika broja grana u mreži (e) i broja grana minimalno povezane mreže (v ‑ 1). • c- broj stvorenih ciklusa • cmax- maksimalni broj ciklusa u mreži

1.2. Izračunavanje stepena povezanosti mreže • Broj ciklusa u mreži c je jednak: c = e − (v − 1) = e − v + 1

• Maksimalni broj ciklusa cmax jednak je maksimalnom broju grana koje je moguće dodati minimalno povezanoj mreži.

1.2. Izračunavanje stepena povezanosti mreže • Minimalno povezana mreža sadrži emin grana. Dodavanjem cmax grana dobija se mreža koja sadrži emax grana.

Pored γ indeksa, kao mera povezanosti mreže koristi se i α indeks koji se definiše kao odnos broja ciklusa c i maksimalnog broja ciklusa cmax:

1.2. Izračunavanje stepena povezanosti mreže Kada je broj grana u mreži e jednak emin, vrednost indeksa α je 0 (minimalno povezana mreža). Maksimalno povezanoj mreži odgovara vrednost α = 1 (tada je e = emax).

Slika 1.18 Mreze G1, G2 i G3

1.2.

Izračunavanje stepena povezanosti mreže

Broj čvorova v u mrežama G1, G2 i G3 je jednak 11. Mreža G1 predstavlja drvo. Ova mreža je minimalno povezana. Broj grana u mreži G1 je:

e1 = emin =10

1.2. Izračunavanje stepena povezanosti mreže Maksimalni broj grana mreže sa 11 čvorova je emax = 3(v‑2) = 27. Vrednost indeksa α u slučaju prve mreže je:

e1 − emin 10 − 10 α1 = = =0 emax − emin 27 − 10

Mreža G2 je nastala iz mreže G1, tako što su dodate tri grane (tanje linije). Vrednost indeksa α u slučaju mreže G2 je: e2 − emin 13 − 10 α2 = = = 0176 . = 17.6% emax − emin 27 − 10

• Broj grana mreže G3 je jednak maksimalnom emax. Samim e3 − broju emin grana emax − emin α = = = 1 = 100% 3 tim je: emax − emin emax − emin

1.3 Merenje dostupnosti u mrežama Dostupnost čvora (aerodrom, autobuska stanica, metro stanica, ..) zavisi od lokacije čvora i rastojanja izmedju pojedinih parova čvorova

Merenje dostupnosti u čvorovima

Merenje dostupnosti u kontinualnom prostoru

 1, ukoliko grana (i, j) postoji u mrezi xi j    0, u ostalim slucajevima

Stepen čvora i:

G(N,A)

Stepen čvora i, D(i) predstavlja osnovnu meru dostupnosti čvora i

A A 0 B 1 C 1 D 0 E 0

B 1 0 1 1 0

C 1 1 0 1 1

D 0 1 1 0 1

E 0 0 1 1 0

Cvor A B C D E

Stepen cvora 2 3 4 3 2

Geografska dostupnost cvora i: dij - duzina najkraćeg puta izmedju čvora i i čvora j

A

B

C

D

E

N

∑d j =1

A B C D E

0 5 3 8 9

5 0 6 8 12

3 6 0 5 6

8 8 5 0 8

9 12 6 8 0

25 31 20 29 35

ij

N

∑ Cvore d

G(i) =I

A B C D E

j =1

ij

Geografska dostupnost

N

5 6.2 4 5.8 7

Geografska dostupnost Geografska dostupnosti čvora predstavlja prosečno najkraće rastojanje izmedju čvora i svih ostalih čvorova mreže. Čvor je utoliko dostupniji ukoliko mu je manja vrednost geografske dostupnosti.

Gustina saobraćajne mreže Pod gustinom saobraćajne mreže se podrazumeva odnos ukupne dužine grana mreže L i ukupne površine prostora S na kome se prostire mreža, tj.: L

ρ=

S

Gustina mreže se najčešće izražava u [km/km2]

Mreža železničkih pruga pre proširenja

S[km 2 ]

Mreža železničkih pruga posle proširenja

S[km 2 ]

1.4.

Prikazivanje mreža u matričnoj formi

• Najčešce se mreža prikazuje u obliku kvadratne matrice u kojoj svakom čvoru mreže odgovara jedna vrsta i jedna kolona.

1.4. 1

Prikazivanje mreža u matričnoj formi 1 2 4 3

2

3

6 5

5

4

Slika 1.19 Mreža G = (N, A) koju treba prikazati pomoću kvadratne matrice

1.4.

Prikazivanje mreža u matričnoj formi

• S obzirom da mreža G = (N, A) ima 5 čvorova, za njeno prikazivanje koristićemo odgovarajuću kvadratnu matricu X koja ima 5 vrsta i 5 kolona. Elementi xij matrice X definišu se na sledeći način:

• Sa slike 1.19 uočavamo da je, na primer, x1,4 = 1 i x3,5 = 0.

1.4.

Prikazivanje mreža u matricnoj formi

• Matrica X pomoću koje je prikazana mreža G = (N, A) sa slike 1.19 glasi: 1 1 0 2 0  X =3 0 4 0  5 1

2 1

3 0

4 1

0 0 0

1 0 0

0 1 0

0

0

0

5 0 0  0 1  0

1.4.

Prikazivanje mreža u matričnoj formi

Za prikazivanje mreža, odnosno grafova u matričnoj formi takodje se koriste i matrice u kojima svakom čvoru odgovara jedna vrsta, a svakoj grani jedna kolona matrice.

Mreža prikazana na slici 1.18 ima 5 čvorova i 6 grana. Za njeno prikazivanje iskoristicemo matricu Y koja ima 5 vrsta i 6 kolona.

1.4.

Prikazivanje mreža u matričnoj formi

• U slučaju kada je m‑ta grana‑grana (i, j), tada je element u preseku i‑te vrste i m‑te kolone jednak +1, elemenat u preseku j‑te vrste i m‑te kolone jednak ‑1, dok su svi ostali elementi matrice Y jednaki nuli.

1.4. Prikazivanje mreža u matričnoj formi • Tako je na primer grana broj 3 u slučaju mreže prikazane na slici 1.19, grana (1, 4). Elemenat y1,3 matrice Y koji se nalazi u preseku prve kolone i treće vrste biće jednak +1, dok ce elemenat y4,3 koji se nalazi u preseku 4‑te vrste i treće kolone da bude jednak ‑1.

1.4.

Prikazivanje mreža u matricnoj formi

Matrica Y za slucaj mreže sa slike 1.18 glasi: links 1 nodes

2

3

4

5

6

1+1 2 −1 X =3 0  4 0 5  0

−1

+1

0

0

0 0 0 +1

0 0 −1 0

+1 −1 0 0

0 0 +1 −1

0 0  +1  −1 0 

1.4.

Prikazivanje mreža u matričnoj formi

• U odredjenim slučajevima u mrežama se javljaju “petlje”, odnosno grane koje započinju i koje se zavrršavaju u istom čvoru (slika 1.19). • U slučaju kada je m‑ta grana‑grana (i, i) tada su svi elementi matrice Y koji pripadaju m‑toj koloni jednaki nuli. Grana broj 4 mreže prikazane na slici 1.19 je grana (2, 2). Samim tim je y1,4 = y2,4 = y3,4 = 0. Matrica Y za slucaj mreže sa slike 1.19 glasi:

1.4.

Prikazivanje mreža u matričnoj formi links 1 nodes

2

3

4

1+1 Y =2  0 3 −1

0 −1 +1

−1 +1 0

0 0  0 

1.4.

Prikazivanje mreža u matričnoj formi 3

1

2 4

1

3

2

Slika 1.20 Mreža sa jednom “petljom”

1.5. Algoritam za konstrukciju razapinjućeg drveta 1

2

3

4

5

Slika 1.21 Pet gradova izmedju kojih je moguće putovati bez presedanja

1.5. Algoritam za konstrukciju razapinjućeg drveta • Pod razapinjućim drvetom mreže G = (N,A) podrazumeva se drvo koje

sadrži sve čvorove početne mreže.

Pretpostavimo da želimo da smanjimo broj parova gradova medjusobno povezanih direktnim saobraćajem. Kako da reorganizujemo mrežu linija železničkog saobraćaja? Dva moguća rešenja proizvoljno odabrana iz skupa mogućih rešenja prikazana su na slikama 1.22(a) i 1.21(b).

1

1.5. Algoritam za konstrukciju razapinjućeg drveta 2

1

2

3

3

5

4 (a )

5

4 (b )

Slika 1.22 Dva prizvoljno odabrana rešenja rekonstrukcije mreže linija železničkog saobraćaja

1.5. Algoritam za konstrukciju razapinjućeg drveta • Kako smo dobili ova rešenja? Da li ima i nekih drugih mogućih rešenja? • Algoritam za konstrukciju razapinjućeg drveta ispituje za svaku granu originalne mreže da li treba da bude uključena u razapinjuće drvo ili ne. • Napomenimo da je redosled kojim se ispituju pojedine grane potpuno proizvoljan. Ispitivanje grane se cesto naziva i bojenjem

1.5. Algoritam za konstrukciju razapinjućeg drveta

Granu koju treba uključiti u razapinjuće drvo treba obojiti zelenom bojom. Crvenom bojom se boje grane koje se ne uključuju u razapinjuće drvo. Prilikom ispitivanja odredjene grane proverava se da li bi uključenje te grane u drvo dovelo do stvaranja ciklusa. Grana se uključuje u drvo ukoliko njeno uključenje u drvo ne stvara ciklus.

1.5. Algoritam za konstrukciju razapinjućeg drveta Prilikom konstruisanja drveta grane već uključene u drvo čine jednu ili više povezanih komponenti. Grana koja se ispituje stvoriće cikluse u drvetu ukoliko oba njena čvora pripadaju istoj komponenti.

1.5. Algoritam za konstrukciju razapinjućeg drveta KORAK 1: Proizvoljno izabrati granu koja nije “petlja” (koja sama po sebi nije ciklus). Obojiti ovu granu u zeleno i oba njena čvora smestiti u komponentu.

1.5. Algoritam za konstrukciju razapinjućeg drveta KORAK 2: Izabrati bilo koju neobojenu granu koja nije “petlja” (ukoliko takva grana ne postoji završiti sa algoritmom, što znači da odgovarajuće pripadajuće drvo ne postoji). Po izvršenom izboru neobojene grane moguće su sledece četiri situacije:

1.5. Algoritam za konstrukciju razapinjućeg drveta (I) Oba čvora ove grane pripadaju istoj komponenti. (II) Jedan čvor grane pripada komponenti a drugi čvor grane ne pripada nijednoj komponenti. (III) Ni jedan ni drugi čvor ne pripadaju nijednoj komponenti. (IV) Čvorovi pripadaju različitim komponentama.

1.5. Algoritam za konstrukciju razapinjućeg drveta U slučaju (I) granu treba obojiti u crveno (ne treba je uključiti u drvo) i vratiti se na početak koraka dva. U slučaju (II) granu treba obojiti u zeleno (uključiti je u drvo). Čvor koji nije pripadao ni jednoj komponenti treba uključiti u komponentu kome pripada čvor na drugom kraju grane.

1.5. Algoritam za konstrukciju razapinjućeg drveta Kada se desi slučaj (III) granu treba obojiti u zeleno (ukljuciti je u drvo), a oba njena čvora treba dodeliti praznoj komponenti. U slučaju (IV) obojiti granu u zeleno (ukljuciti je u drvo), a čvorove iz obe komponente dodeliti jednoj komponenti. Druga komponenta ostaje prazna.

1.5. Algoritam za konstrukciju razapinjućeg drveta KORAK 3: Ukoliko svi čvorovi pripadaju jednoj komponenti završiti sa algoritmom. (Zelene grane u ovom slučaju sačinjavaju pripadajuće drvo). U suprotnom slučaju (kada svi čvorovi ne pripadaju jednoj komponenti) vratiti se na korak 2.

1.5. Algoritam za konstrukciju razapinjućeg drveta • Primenimo algoritam za konstrukciju razapinjućeg drveta na problem rekonstrukcije mreže linija železničkog saobraćaja (slika 1.21) • Neka je redosled kojim ćemo ispitivati grane sledeći: – (1, 2), (4, 5), (1, 4), (2, 5), (1, 3), (2, 3), (3, 4), (3, 5).1 2 zGreen e l e n a Color b o ja c rRed v e n Color a b o ja

Slika 1.23 Uključenje grane (1, 2) u razapinjuće drvo (komponenta 1)

1.5. Algoritam za konstrukciju razapinjućeg drveta k o m p o n e n ta 1

Komponenta 1 1

2 k o m p o n e n ta 2

Komponenta 2

4

5 zGreen e l e n Color a b o ja c rRed v e nColor a b o ja

Slika 1.24 Komponente 1 and 2 po izvršenom ispitivanju grana (1, 2) i (4, 5)

1.5. Algoritam za konstrukciju razapinjućeg drveta Komponenta 1

k o m p o n e n ta 1

1

2

4

5

z eGreen l e n a b Color o ja c r vRed e n a Color b o ja

Slika 1.25 Komponenta 1 po izvršenom ispitivanju grana (1, 2), (4, 5), (1, 4)

1.5. Algoritam za konstrukciju razapinjućeg drveta 1

2

4

5 z eGreen l e n a Color b o ja c r vRed e n Color a b o ja

Slika 1.26 Komponenta 1 po izvršenom ispitivanju grana (1, 2), (4, 5), (1, 4), i (2, 5)

1.5. Algoritam za konstrukciju razapinjućeg drveta 1

2

3

4

5

Slika 1.27 Razapinjuće drvo u slucaju kada su grane ispitivane sledećim redosledom: (1, 2), (4, 5), (1, 4), (2, 5), (1, 3), (2, 3), (3, 4), (3, 5)

1.5. Algoritam za konstrukciju razapinjućeg drveta Pretpostavimo da grane ispitujemo sledećim redosledom: (1, 2), (2, 3), (1, 3), (3, 4), (4, 5), (3, 5), (2, 5), (1, 4). Primenom algoritma za konstrukciju razapinjućeg drveta dobija se pripadajuće drvo prikazano na slici 1.27.

1.5. Algoritam za konstrukciju razapinjućeg drveta 1

2

3

4

5

Slika 1.28 Razapinjuće drvo u slučaju kada su grane ispitivane sledećim redosledom: (1, 2), (2, 3), (1, 3), (3, 4), (4, 5), (3, 5), (2, 5), (1, 4)

1.5. Algoritam za konstrukciju razapinjućeg drveta • Redosled kojim se vrši ispitivanje grana utiče na oblik razapinjućeg drveta. • Pridružimo svakoj grani originalne mreže odredjeni broj koji predstavlja dužinu grane.

1.5. Algoritam za konstrukciju razapinjućeg drveta U odredjenim slučajevima zainteresovani smo za pronalaženje takvog razapinjućeg drveta koje ima najmanju dužinu svih grana. Ovaj problem se rešava primenom algoritma za iznalaženje rayapinjućeg drveta najmanje dužine.

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine

• Neka je dato n gradova koje treba povezati saobraćajnicama. • Najkraće pripadajuće drvo možemo interpretirati kao minimalno potrebnu dužinu puteva kojima ćemo direktno ili indirektno povezati svih n gradova, pretpostavljajući pri tome da svi putevi počinju, odnosno završavaju se u nekom paru gradova.

Prim‑ov algoritam (1957) za iznalaženje najkraćeg razapinjućeg drveta KORAK 1: Sa konstrukcijom najkraćeg razapinjućeg drveta počinje se u nekom proizvoljnom cvoru i. Zatim se pronadje cvor najbliži čvoru i. Neka je to neki cvor j. Cvor j i veza (i, j) se uključuju u najkraće pripadajuće drvo. Zatim se kidaju (ukoliko postoje) grane koje bi onemogućile stvaranje drveta.

KORAK 2: Ukoliko su svi čvorovi povezani, najkraće razapinjuće drvo je pronađeno. Ukoliko postoje još uvek neki izolovani čvorovi prelazimo na korak 3. KORAK 3: Izolovani čvor koji je najbliži do sada formiranom najkraćem ‚razapinjućem drvetu uključuje se zajedno sa odgovarajućom granom u sastav najkraćeg razapinjućeg drveta. Ukoliko postoje grane koje onemogućavaju stvaranje drveta treba ih prekinuti. Po završetku ovog koraka vraćamo se ponovo na korak 2.

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine Primer: Odrediti najkraće razapinjuće drvo transportne mreže prikazane na slici 1.28 (dužine pojedinih grana naznačene su na slici 1.28) primenom Prim‑ovog algoritma.

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje a dužine 9 8

d

4

7

c

e 12

6

11

6

10

7

h

5 f

8

14 g 5 i

b

6

4

9

12 15

j

Slika 1.29 Mreža G za koju treba odrediti razapinjuće drvo najmanje dužine primenom Prim‑ovog algoritma

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine

Započnimo sa konstrukcijom najkraćeg razapinjućeg drveta od čvora a. a 6 e

Slika 1.30 Grana (a, e)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine a 6 e 6 h

Slika 1.31 Grane (a, e) i (e, h)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine a

6 e 6 h 4 j

Slika 1.32 Grane (a, e), (e, h) i (h, j)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine a

b

6

7 e 6 h 4 j

Slika 1.33 Grane (a, e), (e, h), (h, j) i (e, b)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine a b

6

4

7

c

e 6 h 4 j

Slika 1.34 Grane (a, e), (e, h), (h, j), (e, b) i (b, c)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine a

b

6

4

7

c

e 5

6 f

h 4 j

Slika 1.35 Grane (a, e), (e, h), (h, j), (e, b), (b, c) i (c, f)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine a 8 d

b

6

4

7

c

e 5

6 f

h 4 j

Slika 1.36 Grane (a, e), (e, h), (h, j), (e, b), (b, c), (c, f) i (a, d)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje a dužine b 8 6

d

4

7

c

e 5

6 f

h 8 g

4 j

Slika 1.37 Grane (a, e), (e, h), (h, j), (e, b), (b, c), (c, f) , (a, d) i (g, h)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine a

8

b

6

d

4

7

c

e 5

6 f

h 8 g 5 i

4 j

Slika 1.38 Razapinjuće drvo najmanje dužine dobijeno primenom Prim‑ovog algoritma

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine

• Kruskal-ov algoritam

• Kruskal‑ov algoritam (1956) za iznalaženje razapinjućeg drveta najmanje dužine zasnovan je na algoritmu za konstrukciju razapinjućeg drveta. Ovaj algoritam se sastoji od sledećih algoritamskih koraka:

KORAK 1: Napraviti listu sortiranih grana originalne mreže u rastećem poretku njihovih dužina (na prvom mestu liste je najkraća grana, a na poslednjem najduža). U slučaju kada dve ili više grana imaju istu dužinu proizvoljnim redosledom ih uključiti u listu jednu iza druge. KORAK 2: Primeniti algoritam za konstrukciju razapinjućeg drveta ispitujući grane redosledom na kome se nalaze na listi.

Primer: Odrediti najkraće razapinjuće drvo transportne mreže prikazane na slici 1.28 primenom Kruskal‑ovog algoritma. Sortirajmo grane po rastućem poretku njihovih dužina. Redosled kojim treba ispitivati grane prilikom primene algoritma za konstrukciju razapinjućeg drveta je sledeći: (b, c), (h, j), (c, f), (g, i), (a, e), (e, h), (b, f), (e, b), (h, f), (a, d), (g, h), (a, b), (f, j), (d, g), (b, h), (a, g), (i, h), (d, i), (i, j).

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine b c k o m p o n e n ta 11 Komponenta Slika 1.39 Grana (b, c)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine b c k o m p o n e n ta

1

Komponenta 1

k o m p o n e n ta

h

2

Komponenta 2

j

Slika 1.40 Grane (b, c) i (h, j)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine b

c

k o m p o n e n ta 1

Komponenta 1 f

h

k o m p o n e n ta 2

Komponenta 2

j

Slika 1.41 Grane (b, c), (h, j) i (c, f)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine b

c

k o m p o n e n ta 1

Komponenta 1 Komponenta k o m p o n e n ta 3 3

f

h

g

i

k o m p o n e n ta 2

Kompone nta 2

j

Slika 1.42 Grane (b, c), (h, j), (c, f) i (g, i)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine k o m p o n e n ta 1

a

Component 1 b

c

e k o m p o n e n ta 4

Component 4 k o m p o n e n ta 3

f

h

Component 3 g

i

k o m p o n e n t a 22 Component

j

Slika 1.43 Grane (b, c), (h, j), (c, f) i (g, i)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine k o m p o n e n ta 1

a

Component 1

b

c

e

k o m p o n e n ta 3 Component 3

f

h

g

i

k o m p o n e n t a 22 Component

j

Slika 1.44 Grane (b, c), (h, j), (c, f), (g, i) i (e, h)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine k o m p o n e n ta 1

a

Component 1

b

c

e

k o m p o n e n ta 3 Component 3

f

h

g

i

k o mComponent p o n e n t a 22

j

Slika 1.45 Grane (b, c), (h, j), (c, f), (g, i), (e, h) i (b, f)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine k o m p o n e n ta 1

a

Component 1 b

c

e

k o m p o n e n ta 2

f

h

Component 2 g

i

j

Slika 1.46 Grane (b, c), (h, j), (c, f), (g, i), (e, h), (b, f) i (e, b)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine k o m p o n e n ta 1

a

Component 1 b c

e

k o m p o n e n ta 2

f

h

Component 2 g

i

j

Slika 1.47 Grane (b, c), (h, j), (c, f), (g, i), (e, h), (b, f), (e, b) i (h, f)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine k o m p o n e n ta 1

a

d

Component 1 b

c

e

k o m p o n e n ta 2

Component 2

f

h

g

i

j

Slika 1.48 Grane (b, c), (h, j), (c, f), (g, i), (e, h), (b, f), (e, b), (h, f) i (a, d)

1.6. Algoritmi za iznalaženje razapinjućeg drveta najmanje dužine k o m p o n e n ta 1

a

Component 1 b d

c

e

f

h g

z e le n a b o ja

i

j

c r v e n a b o ja

Slika 1.49 Svi čvorovi pripadaju jednoj komponenti

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine KORAK 1: Napraviti listu sortiranih grana originalne mreže u opadajućem poretku (na prvom mestu liste je najduža grana, a na poslednjem najkraća). U slučaju kada dve ili više grana imaju istu dužinu proizvoljnim redosledom ih uključiti u listu jednu iza druge. KORAK 2: Primeniti algoritam za konstrukciju razapinjućeg drveta ispitujući grane redosledom na kome se nalaze na listi.

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine Primer: Odrediti razapinjuće drvo najveće dužine mreže prikazane na slici 1.28.

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine

Sortirajmo grane po opadajućem poretku njihovih dužina. Redosled kojim treba ispitivati grane prilikom primene algoritma za konstukciju razapinjućeg drveta je sledeći: (i, j), (d, i), (i, h), (a, g), (b, h), (d, g), (a, b), (j, f), (a, d), (g, h), (f, h), (b, e), (b, f), (e, h), (a, e), (g, i), (c, f), (b, c), (h, j).

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužinek o m p o n e n t a 1 Component 1

j

i

Slika 1.50 Grana (i, j)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine d

k o m p o n e n ta 1 Component 1

j

i

Slika 1.51 Grane (i, j), (d, i)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine d k o m p o n e n ta 1 Component 1

h

i

j

Slika 1.52 Grane (i, j), (d, i) i (i, h)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 2

d

Component 2

k o m p o n e n ta 1

h

Component 1

g

i

j

Slika 1.53 Grane (i, j), (d, i), (i, h) i (a, g)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 2

k o m p o n e n ta 1

Component 2 b

Component 1

d

h g

i

j

Slika 1.54 Grane (i. j), (d, i), (i, h), (a, g) i (b, h)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 1

b

Component 1

d

h g

i

j

slika 1.55 Grane (i, j), (d, i), (i, h), (a, g), (b, h) i (d, g)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 1

b

Component 1

d

h g

i

j

Slika 1.56 Grane (i, j), (d, i), (i, h), (a, g), (b, h) i (d, g)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 1

b

Component 1

d

f

h g

i

j

Slika 1.57 Grane (i, j), (d, i), (i, h), (a, g), (b, h), (d, g) i (j, f)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 1

b

Component 1

d

f

h g

i

j

Slika 1.58 Grane (i, j), (d, i), (i, h), (a, g), (b, h), (d, g) i (j, f)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine k oComponent m p o n e n ta 11

a b d

f

h g

i

j

Slika 1.59 Grane (i, j), (d, i), (i, h), (a, g), (b, h), (d, g) i (j, f)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 1

b

Component 1

d

f

h g

i

j

Slika 1.60 Grane (i, j), (d, i), (i, h), (a, g), (b, h), (d, g) i (j, f)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 1

b d

Component 1

e

f

h g

i

j

Slika 1.61 Grane (i, j), (d, i), (i, h), (a, g), (b, h), (d, g), (j, f) i (b, e)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 1

b d

Component 1

e

f

h g

i

j

Slika 1.62 Grane (i, j), (d, i), (i, h), (a, g), (b, h), (d, g), (j, f) i (b, e)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

Component komponent11 Component b

d

e

f

h g

i

j

Slika 1.63 Grane (i, j), (d, i), (i, h), (a, g), (b, h), (d, g), (j, f) i (b, e)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 1

b d

Component 1

e

f

h g

i

j

Slika 1.64 Grane (i, j), (d, i), (i, h), (a, g), (b, h), (d, g), (j, f) i (b, e)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a

k o m p o n e n ta 1

b d

Component 1

e

f

h g

i

j

Slika 1.65 Grane (i, j), (d, i), (i, h), (a, g), (b, h), (d, g), (j, f) i (b, e)

1.7. Algoritam za iznalaženje razapinjućeg drveta najveće dužine a b d

c

e

f

h g

i

j

Slika 1.66 Pripadajuće drvo najveće dužine mreže prikazane na slici 1.28.