53. Dat je usmeren graf G=(V,E), tako da V={A, B, C, D, E, F, G}, E={ (A,B), (A,D), (B,E), (B,F), (D,B), (E,D), (F,C), (F,E), (F,G), (G,C) }.
Primeniti DFS obilazak i za svaki čvor iz V prikazati početno vreme/završno vreme. Početno vreme predstavlja vreme prvog nailaska na čvor u DFS algoirtmu. Završno vreme se odnosi na vreme kada su obrađeni svi susedi čvora.
REŠENJE:
Redosled obilaska čvorova grafa DFSom je: ABEDFCG, te je otuda numeracija a/b (gde a je redosled prvog nailaska na čvor,
b je redosled napuštanja čvora)
- A 1/14
- B 2/13
- C 8/9
- D 4/5
- E 3/6
- F 7/12
- G 10/11
SLOŽENOST: Koristi se DFS obilazak koji sadrži jednu globalnu promenljivu vreme koja se postavi na nulu na početku
rada algoritma. Kada se prvi put rekurzivno pozove DFS nad čvorom x, onda se postavi početno vreme čvora x, a kad se iscrpi lista susednosti čvora x, na kraju rekurzivnog poziva, postavi se /završno vreme. Inače, globalna promenljiva vreme se uveća za 1 pri postavljanju svakog početnog i završnog vremena.
DFS potprogram se poziva za svaki čvor poziva samo jednom (samo kad nije posećen), što znači najviše |V| puta. Pri svakom pozivu broj iteracija u unutrašnjoj petlji zavisi od načina određivanja suseda (za matričnu reprezentaciju je složenost onda O(|V|2), a za reprezentaciju listom povezanosti je O(|E|).
54. Dat je usmeren graf G=(V,E), tako da V={A, B, C, D, E, F, G, H}, E={ (A,B), }.
Odrediti: DFS stablo grafa, transponovani graf, jake komponente povezanosti.
REŠENJE:
Neusmeren graf je povezan...
60.Granama grafa G=( {1,2,3,4}, E) su pridružene težine
kao u tabeli:
| grana |
težina |
| (1,2) |
2 |
| (1,3) |
8 |
| (2,3) |
3 |
| (2,4) |
4 |
| (3,4) |
7 |
| (4,1) |
5 |
Odrediti sve najkraće puteve (all shortest paths) između čvorova
ovog grafa.
REŠENJE: Matrica Wi se formira prema algoritmu izloženom
i knjizi u odeljku 6.7
Algoritam SviNajkraciPutevi (W)
{ for (m=0; m<|V|; m++)
for(x=0; x<|V|; x++)
for(y=0;y<|V|;
y++)
if ( W[x,m] +W[m,y] <W[x,y]) W[x,y]= W[x,m] +W[m,y] ;
/*nadjen je kraci put od x do y od predjasnje postavljene duzine*/
}
| W 0 |
1 |
2 |
3 |
4 |
| 1 |
0 |
2 |
8 |
beskonačno |
| 2 |
beskonačno |
0 |
3 |
4 |
| 3 |
beskonačno |
beskonačno |
0 |
7 |
| 4 |
5 |
beskonačno |
beskonačno |
0 |
| W 1 |
1 |
2 |
3 |
4 |
| 1 |
0 |
2 |
8 |
beskonačno |
| 2 |
beskonačno |
0 |
3 |
4 |
| 3 |
beskonačno |
beskonačno |
0 |
7 |
| 4 |
5 |
7 |
13 |
0 |
7=5+2
13=5+8
| W 2 |
1 |
2 |
3 |
4 |
| 1 |
0 |
2 |
5 |
6 |
| 2 |
beskonačno |
0 |
3 |
4 |
| 3 |
beskonačno |
beskonačno |
0 |
7 |
| 4 |
5 |
7 |
10 |
0 |
5=2+3 6=2+4 10=5+5
| W 3 |
1 |
2 |
3 |
4 |
| 1 |
0 |
2 |
5 |
6 |
| 2 |
beskonačno |
0 |
3 |
4 |
| 3 |
beskonačno |
beskonačno |
0 |
7 |
| 4 |
5 |
7 |
10 |
0 |
| W 4 |
1 |
2 |
3 |
4 |
| 1 |
0 |
2 |
5 |
6 |
| 2 |
9 |
0 |
3 |
4 |
| 3 |
12 |
14 |
0 |
7 |
| 4 |
5 |
7 |
10 |
0 |
9=4+5 12=7+5 14=7+7
61. Zadat je težinski graf iz prethodnog zadatka
sa nenegativnim težinama grana. Naći središte grafa.
REŠENJE:Središte grafa je čvor v takav da ima najamanju ekscentričnost.
Ekscentričnost čvora v je maksimum najkraćih rastojanja od svih
čvorova grafa G do čvora v, tj.
ecc(v) = max { W[ i, v] | za svaki čvor i
}
Koraci:
-
primenom algoritma Svi_najkraci_putevi se nadje matrica W najkracih
rastojanja izmedju svih parova cvorova
-
nadju se maksimumi po kolonama matrice W
-
nadje se vrednost minimuma ovih maksimuma i proglasiti za srediste grafa
onaj cvor kojem odgovara ta vrednost
U konkretnom slučaju grafa iz prethodnog zadatka je
pronadjena matrica W u četvrtoj iteraciji:
| W 4 = W |
1 |
2 |
3 |
4 |
| 1 |
0 |
2 |
5 |
6 |
| 2 |
9 |
0 |
3 |
4 |
| 3 |
12 |
14 |
0 |
7 |
| 4 |
5 |
7 |
10 |
0 |
Maksimumi po kolonama su:
-
ecc(1) = 12
-
ecc(2) = 14
-
ecc(3) = 10
-
ecc(4) = 7
Odavde se zaključuje da središte grafa je čvor 4, zato što on ima najmanju
ekscentričnost (čija vrednost jeste 7).
62. Konstruisati algoritam linearne složenosti koji u povezanom neusmerenom
grafu
G=(V,E) pronalazi čvor takav da i nakon izbacivanja tog čvora
iz grafa, opet graf ostaje povezan.
REŠENJE:
Graf je povezan ako (u njegovom neusmerenom) obliku postoji put između ma koja dva čvora. Neusmereni oblik usmerenog grafa G=(V,E) jeste graf G bez orjentacije nad granama.
PODSEĆANJE NA DFS obilazak graf G=(V,E):
Dakle, DFS algoritmom se obilazi graf u dubinu, a ideja je da se za svaki čvor
x iz V tokom obilaska podesi indikator, tj. x.indikator
se postavi na vrednost 1 (markiran je čvor x) kad se u obilasku dođe do x. Obilazak počinje iz proizvoljnog
čvora v, koji se naziva i koren pretrage u dubinu (zato je on i koren DFS stabla). Koren se označava kao posećen. Potom se bira ma koji nezonačeni
čvor w susedan korenu, te se iz čvora w rekurzivno zapocinje pretraga u dubinu (DFS). Iz nekog nivoa rekurzije se izlazi kad se naiđe na
čvor čiji su svi susedi već označeni. Ako se u trenutku okončanja pretrage iz
čvora w, desilo da su svi susedi od v označeni, onda je to kraj pretrage. Inače, bira se sledeći ma koji neoznačeni sused
x čvora v i izvršava pretraga u dubinu počev od x.
Kao rezultat primene DFS, gradi se specijalno povezujuće stablo, tzv. DFS stablo koje ima primenu u mnogim algoritmima koji testiraju neka svojstva grafa.
Koren pretrage u dubinu, tj. čvor v jeste koren DFS stabla.
Obilazeći graf G pretragom u dubinu (DFS) gradi se stablo i označavaju
čvorovi.
- Pri tome neki čvorovi će biti listovi DFS stabla.
- Na početku se stavi da svaki v iz V jeste list, tj. v.indikator=1
- Ako je čvor x iz V povezan sa bar jednim neoznačenim čvorom, onda je to dovoljno da odbacimo
x kao list, tj. x.indikator=0 (jer se nalazi nivo iznad lista)
- na kraju, ako se izbaci neki čvor koji jeste list DFS
stabla, novi graf G' (dobijen iz G bez x) će ostati povezan
Algoritam Izbaciti(G,s)
ulaz: G , s (cvor neusmerenog i povezanog grafa G=(V,E) )
izlaz: za svaki v vazi da v.indikator=1 ako cvor v moze biti izbacen iz G
{
oznaciti s;
s.indikator=1;
for each (s,v)
if not oznacen(v)
{ Izbaciti(G,v);
v.indikator=0;
}
}
Vremenska složenost ovog algoritma (koji koristi DFS pretragu) odgovara
vremenskoj složenosti DFS algoritma za povezane neusmerene grafove, pa
zato jeste linearna po dimenziji ulaza, tj. svaka grana se pregleda do dva puta, te je složenost proporcionalna broju grana,
dok broj rekurzivnih pokretanja je |V|.
Da li izbacivanje čvora može da se obavi za svaki povezan graf G? Zašto?
Naime, za svaki povezan graf postoji odgovarajuće DFS stablo. Svako
stablo ima bar jedan list i to stablo ostaje povezano kada se list izbaci, te
povezani neusmeren graf zaista sadrži čvor koji se može izbaciti, a da novi graf
ostane povezan.
63. Zadat je težinski graf G=(V,E) sa nenegativnim težinama
grana. Za zadata dva čvora i,j skupa V pronaći put minimalne
dužine (a ne samo težinu tog puta).
REŠENJE:
Izmena algoritma Svi_Najkr_putevi (glava 6.7 knjige) , tako da se
formira matrica prethodnika P gde element P[i,j]
pamti
čvor koji je neposredni prethodnik čvora j
na najkraćem putu od čvora i.
Jasno je da:
1. P[i,j]=0 ak je i==j ili ako W[i,j]=beskonacno
2. P[i,j]=i ako i !=j i ako w[i,j] < beskonacno
Dakle, najpre se algortmom Svi_najkraci_putevi u tri for ciklusa ažurira polazna matrica težina W, tako da na kraju
čuva samo najkraće težine (rastojanja) između dva čvora. Tokom ažuriranja matrice W, vrši se i formiranje matrice
čvorova P, tako što:
ako je u k iteracija spoljašnjeg for ciklusa od svih puteva medju čvorovima
i,j koji prolaze kroz međučvorove 1,2,..k nađen trenutno najkraći put, onda:
- ako se čvor k ne nalazi na tom putu, onda su svi medjučvorovi iz skupa {1,2,..,k-1},
pa je to ista ocena najkraćeg puta dobijena iz prethodne (k-1).ve iteracije sa istim prethodnikom
P[i,j]
- ako se čvor k nalazi na tom putu od i do j, onda ovaj put može da se podeli na
puteve od i do k, i na put od k do j. Put izmedju čvorova
i, k prolazi kroz medjučvorove 1..k-1 i on je deo najkraćeg puta od
i do j u k-toj iteraciji, pa je kao u dokazu sa predavanja to i najkraci put od
i do k. Slično se pookazuje da je put od k do j najkraći put od
k do j koji prolazi kroz čvorove 1..k-1.
Dakle, kako je drugi segment puta zajednički, onda prethodnik u k-toj iteraciji
P[i,j] čvora j na najkracem putu je istovetan kao i prethodnik P[k,j] iz (k-1)-ve iteracije
Prema tome, najkraći put od čvora i do čvora j kroz čvorove
1..k se dobija kao manji od najkraćeg puta između i,j kroz medjučvorove
1,..., k-1 i zbira najkraćeg puta između čvorova i,k i puta izmedju k,j kroz
čvorove 1..k-1 sto i jeste u jezgru najugnjezdenijeg for ciklusa.
Potom se od dobijene matrice P rekonstruiše najkraći put u proceduri putanja.
BSO, indeksiramo vrste i kolone od 1..n umesto od 0 do n-1
Algoritam Svi_najkraci_putevi (W)
Ulaz:W(matrica tezina)
Izlaz: W(matrica duzina najkracih puteva), P(matrica prethodecih cvorova na najkracim putevima)
{
for (k=1; k<=n; k++)
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if ( W[i,j]>W[i,k]+W[k,j] )
{ P[i,j]=P[k,j];
W[i,j]=W[i,k] + W[k,j]
}
}
/*iz matrice P rekonstruisemo najkraci put izmedju dva zadata cvora i,j */
Algoritam PUTANJA(i,j)
{
if (i==j)
stampati (i); /*povratak*/
else
if (P[i,j]==0) stampati "(Nema puta izmedju i, j)";
else
{PUTANJA(i, P[i,j] );
stampati (j);
}
}
Na primer, neka rezultujuća matrica P (po grafu iz zadatka 30 i 31) izgleda:
| 0 | 1 | 2 | 2 |
| 4 | 0 | 2 | 2 |
| 4 | 4 | 0 | 3 |
| 4 | 1 | 2 | 0 |
Tad je:
prvi poziv npr. Putanja (1,4)
kako P[1,4] !=0, drugi poziv je Putanja (1,2), jer P[1,4]=2
kako P[1,2] !=0, drugi poziv je Putanja (1,1), jer P[1,2]=1
kako 1==1, stampa se 1
dalje, štampa se 2
dalje, štampa se 4
DAKLE, najkraći put izmedju čvorova 1 i 4 jeste dužine 6 (po zadatku 30),
a ima putanju (((1),2),4)
64. Zadat je težinski usmeren graf G=(V,E) sa nenegativnim težinama
grana. Konstruisati algoritam za određivanje ciklusa minimalne
težine u G.
REŠENJE:
Iskoristićemo rešenje prethodnog zadatka. Naime,
ciklus je put koji počinje i završava se u istom čvoru. Algoritam za nalaženje
svih najkraćih puteva iz prethodnog zadatka se može iskoristiti za nalaženje
najkraćeg ciklusa, tj. puta od čvorova i do čvora j
preko čvorova 1, 2,...,k (najkraći k-put), redom za
k=0,1,2,...,n=|V|.
Jer, nakon izvršenja algoritma
za nalaženje svih najkraćih puteva iz prethodnog zadatka, težina
(dužina, cena, ...) najkraćeg ciklusa je jednaka vrednosti najmanjeg elementa na
dijagonali matrice W, tj. W[k,k] za k=0,1,2,...,n-1,
gde n=|V|.
Ako je potrebno naći ne samo težinu najkraćeg ciklusa, već
i sam put, onda se kao u prethodnom zadataku formira matrica prethodnika P gde element P[i,j]
čuva
čvor koji je neposredni prethodnik čvora j na najkraćem putu od
cvora i.
BSO, indeksiramo vrste i kolone od 0..n-1 umesto od 1 do n
Algoritam Najkraci_ciklus (W)
Ulaz:W(matrica tezina)
Izlaz: W(matrica duzina najkracih puteva), P(matrica prethodecih cvorova na najkracim putevima),
min (duzina najkraceg ciklusa)
{
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
if ( W[i,j]>W[i,k]+W[k,j] )
{ P[i,j]=P[k,j];
W[i,j]=W[i,k] + W[k,j]
}
min=W[0,0]; k=0;
for(i=1;i<n;i++) if (W[i,i]<min) {min=W[i,i]; k=i;}
PUTANJA(k, P[k,k]);
}
/*iz matrice P rekonstruisemo najkraci put izmedju dva zadata cvora i,j */
Algoritam PUTANJA(i,j)
{
if (i==j)
stampati (i); /*povratak*/
else
if (P[i,j]==0) stampati "(Nema puta izmedju i, j)";
else
{PUTANJA(i, P[i,j] );
stampati (j);
}
}
65. Zadat je težinski usmeren graf G=(V,E) u kom neke
grane imaju negativnu težinu. Konstruisati efikasan algoritam za utvrđivanje
da li graf sadrži ciklus negativne
težine u G (dovoljno je dati rezultat u obliku odgovora DA/NE).
REŠENJE:
Primenimo ponovo algoritam Svi_Najkr_putevi (glava 6.7 knjige),
ali ga modifikujmo tako da algoritam vrati odgovor DA kada naidje na dijagonalni
element matrice koji je negativan.
BSO, indeksiramo vrste i kolone od 0..n-1 umesto od 1 do n
Algoritam Negativan_ciklus (W)
Ulaz:W(matrica tezina)
Izlaz: DA/NE u slucaju da ima/nema negativnog ciklusa
{
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
if ( W[i,j]>W[i,k]+W[k,j] )
W[i,j]=W[i,k] + W[k,j]
for(i=0;i<n;i++) if (W[i,i]<0) return DA;
return NE;
}
6x. Zadat je aciklički usmeren graf G=(V,E).
Konstruisati algoritam linearne složenosti koji utvrđuje da li u G
postoji neki prost put koji sadrži sve čvorove grafa.
REŠENJE:
Put je prost, ako se svaki čvor pojavljuje
u njemu samo jednom.
Hamiltonov put je prosti put u kom se svaki čvor grafa pojavljuje tačno
jednom.
U ovom zadataku zahtev je da se konstruiše algoritam za pronalazak
Hamiltonovog puta u grafu G.
Ideja je da se konstruiše topološki redosled čvorova grafa G, a potom
se proveri da li postoji put tako što se proveri da li susedni čvorovi u
topološkom redosledu jesu putno povezani. Ukoliko su povezani, onda Hamiltonov
put čine topološki uređeni čvorovi.
Problem topološkog sortiranja je problem formiranja rasporeda čvorova u grafu
G tako da ako se svi čvorovi grafa numerišu brojevima
od 1 do n=|V|, onda ako čvor v
je numerisan sa k svi čvorovi do kojih postoji
usmeren put iz v imaju numeraciju veću od k.
U glavi 6.4 knjige je prikazan algoritam za topološko sortiranje acikličkog
usmerenog graga G.
Algoritam TOPSORT(G)
ulaz: G
izlaz: v.Num (numeracija cvora v u toploskom redosledu)
{
pomocu DFS
obilaska stabla naci ulazni stepen svakog cvora, tj. v.InDeg
Broj=0; /*tekuci
redni broj*/
for(i=1; i<=n; i++)
if (v[i].InDeg==0) staviti v[i] u listu;
while (lista nije prazna)
{
uzmi cvor v sa liste;
Broj++; v.Num=Broj;
for svaka grana (v,w)
{ w.InDeg--;
if (w.InDeg==0) stavi w u listu;
}
}
}
Algoitam toploškog sortiranja je složenosti O( |E| + |V| ),
tj. linearne složenosti kod grafova.
67. Zadat je težinski graf G=(V,E) čije grane mogu imati i negativne
težine. Naći najkraća rastojanja od polaznog čvora grafa G do svih
ostalih (bez smanjenja opštosti obeležimo taj čvor sa 1).
REŠENJE:
Koristimo Dijkstrin
algoritam za nalaženje težina najkraćih puteva od zadatog čvora 1 do ostalih
čvorova u grafu (glava 6.5 u knjizi) tako što ga modifikujemo da
radi i nad težinski grafom G=(V,E) čije grane mogu imati i negativne
težine.
Algoritam Dijkstra_negativni(G,W)
ulaz: G=(V,E) (tezinski graf sa negativnim tezinama), W(matrica tezina, indeksirana po i=1..|V| ) )
izlaz:D (niz gde d[i] je najkrace rastojanje od polaznog cvora 1 do cvora i, gde i=1..|V| )
T(niz gde t[i] je cvor koji je prethodnik cvora i na najkracem putu od cvora 1 )
{
for (i=2; i <= n; i++)
{
d[i]=w[1,i];
if (w[1,i] != beskonacno) t[i]=1;
else t[i]=0;
}
for (k=1; k<=n-1; k++)
for svaka grana (u,v)
if (d[u] +w[u,v] < d[v])
{
d[v]=d[u]+w[u,v];
t[v]=u;
}
for svaka grana (u,v)
if (d[u] +w[u,v] < d[v]) return false;
return true;
}
Na vremensku složenost algoritma utiču dva for ciklusa gde se za k=1..n-1
ažurira za svaka granu niyove D,T (ako je potrebno), te je onda složenost
O(
n |E| ).
68. Dat je usmereni graf G=(V,E) sa skupom čvorova V={1,2,3,4,5,6,7,8,9}
i skupom grana E sa težinama kao na slici. Odrediti težine najkraćih
puteva od čvora 1 do ostalih čvorova u grafu.
REŠENJE Koristimo Dijkstrin
algoritam za nalaženje težina najkraćih puteva od zadatog čvora 1 do ostalih
čvorova u grafu (glava 6.5 u knjizi).
Algoritam Najkr_putevi (G,v)
ulaz: G=(V,E) (tezinski usmeren graf), v (polazni cvor)
izlaz: za svaki cvor w je sa w.SP oznacena tezina najkraceg puta od v do w
(* uz pretpostavku da su sve tezine grana grafa nenegativne *)
begin
for svi cvorovi w do
w.oznaka=false;
w.SP=*; (* za sada tezina je beskonacna *)
v.SP=0;
while postoji neoznacen cvor do
neka w je neoznacen cvor sa najmanjom vrednoscu w.SP
w.oznaka=true;
for sve grane (w,z) takve da z je neoznacen do
if w.SP + tezina(w,z) < z.SP then z.SP=w.SP + tezina(w,z);
end
Prikaz postupka i rešenje je naveden u tabeli .
Najpre se popuni 1. red tabele tako da se unesu vrednosti
težina grana sa slike grafa.
Potom se izabere njamanja težina te vrste. Konkretno to je
ovde vrednost 2 čvora 8.
Potom se označi čvor 8 i formira 2. red tabele u kom se menjaju
težine onih puteva koje bivaju kraće ako se u njih uključi čvor 8.
I tako redom sve dok postoji neoznačen čvor.
| označeni |
čvor w
(najmanje SP) |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| 1 |
- |
15 |
14 |
10 |
11 |
6 |
* |
2 |
* |
| 1,8 |
8 |
11 |
14 |
10 |
11 |
5 |
10 |
2 |
7 |
| 1,6,8 |
6 |
11 |
14 |
10 |
9 |
5 |
9 |
2 |
7 |
| 1,6,8,9 |
9 |
10 |
14 |
10 |
9 |
5 |
9 |
2 |
7 |
| 1,5,6,8,9 |
5 |
10 |
14 |
10 |
9 |
5 |
9 |
2 |
7 |
| 1,,5,6,7,8,9 |
7 |
10 |
14 |
10 |
9 |
5 |
9 |
2 |
7 |
| 1,2,5,6,7,8,9 |
2 |
10 |
12 |
10 |
9 |
5 |
9 |
2 |
7 |
| 1,2,4,5,6,7,8,9 |
4 |
10 |
12 |
10 |
9 |
5 |
9 |
2 |
7 |
| 1,2,3,4,5,6,7,8,9 |
3 |
10 |
12 |
10 |
9 |
5 |
9 |
2 |
7 |
69. Neka G=(V,E) je neusmeren graf. Skup grana F podskup od U
naziva se skup povratnih grana ako svaki ciklus u G sadrži bar jednu granu iz F.
Konstruisati algoritam za nalaženje minimalnog skupa povratnih grana.
REŠENJE:
Povezujuće stablo neusmerenog
grafa G je njegov podgraf koji je stablo i sadrži sve čvorove
iz G.
Kako svaki ciklus u G mora da sadrži jednu granu iz
skupa grana F => skup grana E\F ne sadrži niti jedan
ciklus. Dakle, što je manji skup F, to je veći skup E\F.
Maksimalni skup grana
grafa bez ciklusa formira povezujuće stablo kod povezanih grafova
(odnosno povezujuću šumu kod nepovezanog grafa). Dakle, minimalni skup F je
komplement ma kog povezujućeg stabla grafa. (videti glavu 6.6 udžbenika).
70.
Neka e je grana maksimalne težine u nekom ciklusu grafa G=(V,E).
Dokazati da postoji MCST grafa G'=(V,
E\{e}) koje je istovremeno i MCST grafa G.
REŠENJE:
PODSEĆANJE:
Prema glavi 6.6
knjige Algoritmika MCST (minimum-cost spanning tree) je minimalno
povezujuće stablo, tj. povezujuće stablo čija suma težina (cena) grana je
minimalna.
U knjizi je prikazan algoritam za konstrukciju MCST koji
nalikuje Dijkstra algoritmu za nalaženje najkraćih puteva od zadatog čvora
grafa. Složenost algoritma je O( (|E|+|V|) log |V|)
Neka T je MCST zadatog grafa G koje sadrži granu
e=(x,y) najveće težine u nekom ciklusu C. Ako se
ukloni grana e, onda iz stabla T nastaju stabla T1, T2, tako da je na
primer čvor x u T1, čvor y u T2.
Neka P je put od x do y koji nastaje kada se iz cilusa C ukloni grana e.
Na tom putu postoji grana e1 koja povezuje stabla T1 i T2, tj. grana čiji jedan
kraj mora biti u T1, a drugi kraj u T2. Težina grane e1 jednaka je težini grane
e (jer ako bi težina grane e1 bila manja od težine grane e, onda bi povezujuće
stablo T bez grane e koje sadrzi
granu e1 imalo manju cenu od stabla T).
Dakle, stablo (T\{e})
sa granom {e1} je
MCST, ali ne sadrzi granu e.
71. Neka je G=(V,E)
neusmeren težinski graf i neka T=(V,F) je podgraf koji se
sastoji od svih grana na najkraćim putevima od čvora x iz V.
Ako se težine grana G povećaju za jednu istu konstantu w, da li T ostaje
i dalje stablo najkraćih puteva od x.
REŠENJE: Odgovor je NE.
Na primer, neka u grafu T sa
korenom x i čvorovima x, y, z (trougao XYZ)
grana (x,y) ima
težinu 2
grana (x,z) ima težinu 5
grana (y,z) ima težinu 2
To znači da primenom Dijkstra
algoritma nad G smo imali da u odnosu na granu (x,z) kraći put od x do z
preko čvora y ima težinu 4=2+2
Neka je w=5. Dakle, sada u grafu T sa korenom x
grana (x,y) ima težinu 7
grana (x,z) ima težinu 10
grana (y,z) ima težinu 7
To znači da put od x do z preko
čvora y ima težinu 14=7+7, ali od njega je kraća
grana (x,z) sa težinom 10
72.
Neka G=(V,E)
je neusmeren povezan graf koji ima k čvorova i svi su
neparnog stepena. Dokazati da broj k je paran.
Neka d(1), d(2), ..., d(k) su stepeni čvorova.
Kako su oni neparni brojevi, možemo ih predstaviti kao d(i)=2*xi
+1, gde xi
su celi brojevi
Otuda zbir stepena svih k čvorova DEG=d(1)
+ d(2) + ... +
d(k) = 2*(x1 + x2 + xk ) + k
(*)
LEMA: DEG je paran broj.
Dokaz leme: Neka broj grana grafa |E|=s. Tada DEG=2*s, jer svaka grana
sadrži tačno dva čvora i pri računanju zbira stepena svih
čvorova (DEG) svaka grana se broji tačno dva puta, te je DEG dva puta veći od
ukupnog broja grana.
Dakle, prema (*) i prema lemi važi:
DEG=DEG
2*(x1 + x2 + xk ) + k
= 2*s
k = 2*(s- (x1 + x2 + xk )
)
Odavde zaključujemo da k je paran broj.
73. Dat je usmereni graf G=(V,E) i njegov čvor v skupa
V. Konstruisati algoritam složenosti O( |E| + |V| ) koji ispituje
da li
G jeste korensko stablo sa korenom v. Smatrati da su
u korenskom stablu grane usmerene od korena ka listovima.
REŠENJE:
Korensko stablo jeste usmereno stablo koje poseduje posebno izdvojen čvor koji se zove koren, a sve grane su usmerene od korena.
Kako ulazni stepen svakog čvora nije veći od jedan,
usmeren graf je stablo akko je povezan i nema (usmerene) cikluse.
Na zadati usmeren graf G=(V,E) treba primeniti algoritam za obilazak
stabla smatrajuci pri tome da je cvor v njegov koren i brojeci
cvorove kroz koje se prolazi.
Ukoliko pri tom obilasku broj čvorova
kroz koje se prošlo bude veći od |V|, graf G ima ciklus(e), pa
nije stablo;
ukoliko se obilazak zavrči sa brojem čvorova kroz
koje se prošlo manjim od |V|, graf G nije povezan, pa nije stablo;
inače graf G jeste stablo.
Algoritam obilazak1(G,v})
ulaz: G=(V,E) (usmeren graf), v (cvor grafa G)
izlaz: broj ( brojac cvorova kroz koje se proslo)
{
markiraj v;
broj=broj+1 ;
ako je broj manji ili jednak od broja cvorova grafa G onda
za sve grane (v,w) do
if markiran(w) return -1;
else
obilazak1(G,w);
return broj;
}
Algoritam provera1(G,v)
ulaz: G=(V,E) (usmeren graf), v(cvor grafa G)
izlaz: odgovor na pitanje da li je graf G sa korenom v stablo
{
broj:=0 ;
obilazak1(G,v);
ako je broj manji od broja cvorova grafa G onda
write('graf G nije povezan');
ako je broj veci od broja cvorova grafa G onda write('graf G ima ciklus(e)')
inace write('graf G je stablo');
}
74. Neka je G = (V,E) usmereni graf i neka T je DFS stablo grafa G.
G sadrži usmereni ciklus ako i samo ako G sadrži povratnu granu (u odnosu na
T). Dokazati.
REŠENJE:
DFS pretraga se vrši i kod usmerenih grafova sličnim mehanizmom kao i kod neusmerenih grafova,
ali usmerena DFS stabla imaju drugačije osobine, tj. postoji četiri tipa grana:
- grane stabla
- povratne grane
- direktne grane
- poprečne grane
Prve tri grane povezuju dva čvora grafa, tako da jedan je potomak drugog u DFS stablu.
Preciznije, grana stabla povezuje oca sa sinom.
Povratna grana povezuje potomka sa pretkom.
Direktna grana povezuje pretka sa potomkom.
Poprečne grane povezuju čvorove koji nisu srodnici u stablu i prema dokazanoj lemi sa predavanja, one moraju biti usmerene zdesna ulevo, te otud i naziv grana ulevo.
Za DFS Stablo neusmerenog grafa, pak važi: grane povezanog neusmerenog grafa ne mogu biti poprečne grane za DFS stablo, tj. ne mogu povezivati
čvorove na različitim putevima od korena.
Prema DFS odlaznoj numeraciji (tj. v.Post je redni broj čvora v pri odlaznoj
numeraciji čvorova grafa u DFS obilasku grafa tj. to je redni broj čvora u
redosledu napuštanja u izlaznoj obradi), za usmereno stablo važi:
- Ako grana (u,v) jeste grana stabla ili direktna, onda: v.Post < u.Post (jer,
v je potomak od u)
- Ako grana (u,v) jeste poprečna, onda: v.Post < u.Post
(jer, v je levo od u)
- Ako grana (u,v) jeste povratna i v!=u, onda: v.Post >
u.Post (jer, v je pravi predak od u)
- Ako grana (u,v) jeste povratna i v==u (jer petlja
jeste povratna grana), onda: v.Post = u.Post (jer, v je strogo predak od u)
Dakle, za povratnu granu (u,v) v.Post >=u.Post
Lema1: Grana (u, v) usmerenog grafa G je povratna ako i
samo ako prema odlaznoj numeraciji (DFS) čvor u prethodi čvoru v, tj. u.Post
<= v.Post
<=
Ako je grana (u,v) povratna, onda ona zajedno sa granama stabla na putu od u do v zatvara ciklus.
=>
Takođe je tačno i suprotno tvrđenje: ako u grafu postoji ciklus, tada u njemu mora da postoji povratna grana.
Zaista, pretpostavimo da u grafu postoji ciklus koji čine grane
(v1, v2), (v2,v3), . . . (vk, v1)
Ako k=1 (tj. ciklus je petlja), tada je grana (v,v) povratna.
Ako je k veće od jedan, pretpostavimo da nijedna od grana
(v1, v2), (v2,v3), . . . (vk-1, vk) nije povratna.
Po Lemi 1, onda važi da v1.Post > v2.Post > . . .
vk.Post,
odnosno vk.Post < v1.Post, pa je grana (vk,v1) povratna.
Time je dokazano da u svakom ciklusu postoji povratna grana.
75.
Dat je bipartitivni graf G čiji su
čvorovi a, b, c, d, e, f, g
odnosno 1, 2, 3, 4, 5, 6, 7 i
čiji skup grana je
{(a,1), (a,2), (a,5), (b,1), (b,2), (b,6), (c,1), (c,2), (c,3), (c,7), (d,1), (d,2), (e,1), (e,4), (f,5),
(g,6)}.
Odrediti optimalno bipartitivno uparivanje.
PODSEĆANJE:
Za zadati neusmeren graf G, uparivanje je skup
disjunktnih grana (grana bez zajedničkih čvorova).
Čvor koji ne pripada niti jednoj grani uparivanja zove se
neuparen čvor.
Savršeno uparivanje je uparivanje u kom su svi čvorovi upareni.
Optimalno uparivanje je uparivanje sa maksimalnim brojem grana. Ovaj
zadatak se bavi jednim tipom optimalnog uparivanja.
Ako
G=(V,E,U) jeste bipartitivni graf u kome V, U su disjunktni skupovi čvorova, E
je skup grana koje povezuje neke čvorove iz V sa nekim čvorovima iz U.
Teorema o alternirajućem putu:
Bipartitivno uparivanje S jeste optimalno
<= > u grafu G
ne postoje alternirajući putevi za njega.
Alternirajuci put X za dato uparivanje S jeste put od neuparenog
čvora v iz V do neuparenog
čvora u iz U, pri
čemu su grane puta X naizmenično u E\S, odnosno u S.
Tj. prva grana (v,x) puta X ne pripada S, jer v je neuparen, druga grana (x,y) pripada S i
tako dalje do grane (z,u) puta X koja ne pripada S.
Teorema o alternirajućem putu određuje korake algoritma za
pronalazak optimalnog bipartitivnog
uparivanja. Naime, ma koje uparivanje
koje nije optimalno ima alternirajući put, a alternirajući put proizvodi
povećano uparivanje. Dakle, na početku algoritma
pronadje se uparivanje S dodavanjem grana dokle god je to moguće. Potom se
pronadje alternirajući put za uparivanje S, a na osnovu njega se vrši
povećavanje uparivanj sve dok nedobijemo novo uparivanje S za koje nema
alternirajućih puteva. Dobijeno uparivanje je tada optimalno.
Dakle, neka je uparivanje M={(a,1), (b,2), (c,3), (e,4), (f,5), (g,6)}.
Na slici je prikazano da zbog pronalaska alternirajuceg puta u G, usmeravamo
grane G tako da one koje su u M budu udesno, a one koje nisu orjentisane su
ulevo. Neupareni su čvorovi 7, d i pokušavamo da nadjemo put od
7 do d. Ali takav put ne postoji, jer od 7 se može samo do čvora c, a od njega
dalje samo do čvora 3, ali ne i čvora d. Dakle, M je optimalno uparivanje.
Može se do uparivanja M doći i ako se kao polazno
uparivanje uspostavi uparivanje N={(a,5), (b,2), (c,3), (e,4),
(g,6)}, jer bi se uočio alternirajući put f, 5, a.
76.
Dat je bipartitivni graf G čiji su
čvorovi a, b, c, d, e, f, odnosno 1, 2, 3, 4, 5, 6 i
čiji skup grana je
{(a,1), (b,1), (b,2), (b,3), (c,4), (d,3), (d,6), (e,4), (f,5), (f,6)}.
Odrediti optimalno bipartitivno uparivanje.
REŠENJE:
Za zadati neusmeren graf G, uparivanje je skup
disjunktnih grana (grana bez zajedničkih čvorova).
Čvor koji ne pripada niti jednoj grani uparivanja zove se
neuparen čvor.
Savršeno uparivanje je uparivanje u kom su svi čvorovi upareni.
Optimalno uparivanje je uparivanje sa maksimalnim brojem grana. Ovaj
zadatak se bavi jednim tipom optimalnog uparivanja.
Ako
G=(V,E,U) jeste bipartitivni graf u kome V, U su disjunktni skupovi čvorova, E
je skup grana koje povezuje neke čvorove iz V sa nekim čvorovima iz U.
Na primer, slika 5 prikazuje bipartitivni graf sa skupom čvorova
koga čine dva disjunktna podskupa {1, 2} i {3, 4, 5}, gde svaka grana grafa
povezuju čvorove iz različitih podskupova.
Slika5 Optimalno bipartitivno
uparivanje M je uparivanje sa maksimalnim brojem grana u bipartitivnom grafu.
Neka je uparivanje S={ a-1, b-3, c-4,
d-6}.
Može se uočiti da postoji alternirajući put za ovo
uparivanje i to je put a-1-b-3-d-6-f. Kako postoji alternirajući put=>ovo uparivanje u G nije
optimalno.
Granu b-3 i dodamo nove grane b-2, f-6. Novo uparivanje S={
a-1, b-2, c-4, d-3, f-6}.
Novo uparivanje nema aternirajućih puteva (jer bi tačno jedan takav
bio e-4-c-5, ali on ne može da se realizuje u G)=> uparivanje
S jeste optimalno. (broj grana u uparivanju je pet i
jeste optimalno , jer postoji tačno po jedna grana za
čvor c, odnosno e i to do čvora 4)
e-mail: Jelena Grmuša
Poslednja
izmena: mart 2003.
URL: http://www.matf.bg.ac.yu/~jelenagr/op/v6.htm
