Algoritmicagrafurilor-Cursul4olariu/curent/AG/files/agr4.pdf · G = ( V; E) este un digraf fără...

C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms *

Algoritmica grafurilor - Cursul 4

25 octombrie 2019

Algoritmica grafurilor - Cursul 4 25 octombrie 2019 1 / 44


Cuprins

1 Probleme de drumuri în digrafuriDrumuri de cost minim - Problema P2 pentru dags: sortareatopologicăDrumuri de cost minim - Problema P2 pentru costuri nenegativeDrumuri de cost minim - Problema P2 pentru costuri realeDrumuri de cost minim - Rezolvarea problem P3Înmulţirea (rapidă) a matricilor

2 Exerciţii pentru seminarul de săptămâna următare



Drumuri de cost minim - Problema P2 pentru dags

Un digraf aciclic (dag) este un digraf fără circuite.O ordonare topologică a (nodurilor) unui digraf G = (V ;E), cujGj = n , este o funcţie injectivă ord : V ! f1; 2; : : : ;ng (ord [u ] =

numărul de ordine al nodului u , 8u 2 V ) aşa încât

uv 2 E ) ord [u ] < ord [v ];8uv 2 E :

Lema 1G = (V ;E) este un digraf fără circuite dacă şi numai dacă admite oordonare topologică.




Proof: "(" Fie ord o ordonare topologică a lui G . Dacă C =

(u1;u1u2;u2; : : : ;uk ;uku1;u1) este un circuit în G , atunci, din propri-etatea funcţiei ord , obţinem contradicţiea

ord [u1] < ord [u2] < : : : < ord [uk ] < ord [u1]:

")" Fie G = (V ;E) un digraf de ordin n fără circuite. Arătămprin inducţie după n că G are o ordonare topologică. Pasul induc-tiv:let v0 2 V ;while (d�G (v0) 6= 0) dotake u 2 V aşa încât uv0 2 E ;v0 u ;

return v0.




Evident, deoarece G nu are circuite şi V este finită, algoritmul se ter-mină şi în nodul returnat, v0, nu mai intră arce. Digraful G � v0 nuare circuite şi din ipoteza inductivă are o ordonare topologică ord 0. Or-donarea topologică a lui G este

ord [v ] =

(1; dacă v = v0

ord 0[v ] + 1; dacă v 2 V n fv0g:

�

Din demonstraţia de mai sus obţinem următorul algoritm pentru re-cunoaşterea unui dag şi construcţia unei ordonări topologice în cazulinstanţelor “yes”:Input: G = (f1; : : : ;ng;E) digraf cu jE j = m .Output: "yes" dacă G este dag şi o ordonare topologică ord ; "no"altfel.




construct the array d�G [u ]; 8u 2 V ;count 0; S fu 2 V : d�G [u ] = 0g; // S este o coadă sau o stivă;while (S 6= ?) dov pop(S); count ++; ord [v ] count ;for (w 2 A[v ]) dod�G [w ]��;if (d�G [w ] = 0) thenpush(S ;w);

// complexitatea timp O(n +m);if (count = n) thenreturn "yes" ord ;

return "no";




P2 Dat G = (V ;E) digraf; a : E ! R; s 2 V :

Determină P�si 2 Psi ;8i 2 V ; a. î. a(P�

si ) = min fa(Psi ) : Psi 2 Psig

P2 cu G = (f1; : : : ;ng;E) dag, cu ord [i ] = i , 8i 2 V , şi s = 1.Condiţia (I) este satisfăcută şi sistemul (B) se rezolvă prin "substituţie".u1 0; before [1] 0;for (i = 2;n) doui 1; before [i ] 0;for (j = 1; i � 1) do

if (ui > uj + aji ) thenui uj + aji ; before [i ] j ;

// complexitatea timp O(n2);



Drumuri de cost minim - Problema P2 pentru costuri nenegative

P2 Dat G = (V ;E) digraf; a : E ! R; s 2 V :

Determină P�si 2 Psi ;8i 2 V ; a. î. a(P�

si ) = min fa(Psi ) : Psi 2 Psig

P2 cu a(e) > 0;8e 2 E .Condiţia (I) este satisfăcută şi sistemul (B) se poate rezolva cu algorit-mul lui Dijkstra, care are următorul invariant: S � V şi

(D)

(8i 2 S ui = min fa(Psi : Psi 2 Psig

8i 2 V n S ui = min fa(Psi : Psi 2 Psi ;V (Psi ) n S = figg

Iniţial S = fsg şi în fiecare dintre cei n�1 paşi un nod nou este adăugatla S , obţinând S = V . Astfel, datorită invariantului (D) de mai sus,P2 este rezolvată.




Algoritmul lui DijkstraS fsg; before [s ] 0; us 0;for (i 2 V n fsg) doui asi ; before [i ] s ; // (are loc D)

while (S 6= V ) dofind j � 2 V n S s. t. uj � = min fuj : j 2 V n Sg;S S [ fj �g;for (j 2 V n S) do

if (uj > uj � + aj �j ) thenuj uj � + aj �j ; before [j ] j �;




Demonstraţia corectitudinii algoritmului lui DijkstraDeoarece (D) are loc după pasul de iniţializare, trebuie să demonstrămcă dacă (D) are loc înaintea iteraţiei while curente, atunci (D) are loc şiînaintea iteraţiei următoare.Fie S � V şi u1; : : :un satisfăcând (D) înaintea iteraţiei while curente.Arătăm a mai întâi că dacă j � este astfel încât uj � =

min fuj : j 2 V n Sg, atunci

uj � = min fa(Psj �) : Psj � 2 Psj �g:

Să presupunem că 9P1sj � 2 Psj � aşa încât a(P1

sj �) < uj � . Deoarece S şiui satisfac (D), avem

uj � = min fa(Psj �) : Psj � 2 Psj � ;V (Psj �) n S = fj �gg:

Urmează că V (P1sj �) n S 6= fj

�g; fie k primul nod de pe P1sj � (începând

cu s) aşa încât k =2 S .




Demonstraţia corectitudinii algoritmului lui Dijkstra (cont.)Atunci a(P1

sj �) = a(P1sk ) + a(P1

kj �). Din modul de alegere a lui k , avemV (P1

sk ) n S = fkg şi, deoarece (D) este satisfăcută, avem a(P1sk ) > uk .

Obţinem că uj � > a(P1sj �) > uk +a(P1

kj �) > uk (costurile sunt > 0, decia(P1

kj �) > 0. Dar aceasta contrazice alegerea lui j �.Urmează că în iteraţia curentă, după asignarea S S [ fj �g, primaparte din (D) are loc.Bucla for de după această asignare este necesară pentru a asigura parteaa doua din(D) după iteraţia while: 8j 2 V n (S [ fj �g)

min fa(Psj ) : Psj 2 Psj ;V (Psj ) n (S [ fj �g) = fj gg =

min fmin fa(Psj ) : Psj 2 Psj ;V (Psj ) n S = fj gg(= uj );

min fa(Psj ) : Psj 2 Psj ;V (Psj ) n S = fj ; j �gg(= �j )g :




Demonstraţia corectitudinii algoritmului lui Dijkstra (cont.)Primul argument din minimul de mai sus este uj (vechea valoare dinain-tea buclei for); fie �j cel de-al doilea argument.Fie P1

sj un drum pentru care �j = a(P1sj ) cu j � 2 V (P1

sj ) şi V (P1sj n(S [

fj �g) = fj g; avem �j = a(P1sj �) + a(P1

j �j ). Deoarece am demonstrat căS [fj �g satisface prima parte din (D), urmează că a(P1

sj �) = uj � şi deci�j = uj � + a(P1

j �j ).Dacă a(P1

j �j ) 6= aj �j , urmează că există i 2 V (P1j �j )\S , i 6= j �. De unde

uj 6 a(P�si ) + a(P1

ij ) = ui + a(P1ij ) 6 a(P1

si ) + a(P1ij ) = a(P1

sj ) = �j .Am obţinut că singura posibilitate de a avea �j < uj este când a(P1

j �j ) =

aj �j , în acest caz �j = uj � + aj �j < uj , care este testul din bucla for aalgoritmului (uj este vechea valoare dinaintea buclei for).

�




Complexitatea timp a algoritmului lui DijkstraDeoarece bucla for din cel de-al doilea pas poate fi înlocuită echivalentcu

for (j 2 N+G (j �)) do

if (uj > uj � + aj �j ) thenuj uj � + aj �j ; before [j ] j �;

timpul general necesar algoritmului pentru a actualiza valorile uj este

O(X

j �2V nfsg

d+G (j �)) = O(m):

Urmează că complexitatea timp este dominată de secvenţa de deter-minări a minimelor uj � .




Complexitatea timp a algoritmului lui Dijkstra

Dacă alegerea minimului uj � este făcută prin parcurgerea lui(uj )j2V nS , atunci algoritmul se execută în O((n � 1) + (n � 2) +� � �+ 1) = O(n2).

Dacă valorile lui uj pentru j 2 V n S sunt ţinute într-o coadăcu priorităţi (e.g. heap) atunci extragerea fiecărui minim necesităO(1), dar timpul necsar execuţiei tuturor reducerilor uj este în cazulcel mai nefavorabilO(m logn) - suntO(m) reduceri posibile, fiecarenecesitând O(logn) pentru întreţinerea heap-ului (Johnson,1977).

Cea mai bună implementare se obţine folosind o grămadă (heap)Fibonacci cu o complexitate timp de O(m + n logn) (Fredman &Tarjan, 1984).




Remarci 1Pentru a rezolva problema P1 folosind algoritmul lui Dijkstra,adăgăm un test de oprire a execuţiei când nodul t este introdusîn S . în cazul cel mai nefavorabil complexitatea rămâne aceeaşi.

O euristica interesantă care dirijează căutarea spre t se obţine cuajutorul unui estimator consistent, i. e. o funcţie g : V ! R+

care satisface condiţiile:

(i) 8i 2 V , ui + g(i) 6 min fa(Pst ) : Pst 2 Pst şi i 2 V (Pst )g

(ii) 8ij 2 E ; g(i) 6 aij + g(j ).

Evident, g(i) = 0, 8i este un estimator consistent trivial.




Remarci 2Dacă V (G) este a mulţime de puncte dintr-un spaţiu Euclidean,atunci, luând g(i) = distanţa Euclideană de la i la t , obţinem unestimator consistent dacă sunt satisfăcute şi condiţiile din (ii).

Dacă g este un estimator consistent, atunci alegerea lui j � în algo-ritmul lui Dijkstra se face astfel

uj � + g(j �) = min fuj + g(j ) : j 2 V n Sg:

Corectitudinea demonstraţiei este similară cu cea dată pentrug(i) = 0, 8i .




Remarci 3În descrierea algoritmului lui Dijkstra se foloseşte matricea de cost-adiacenţă. Pentru digrafuri foarte mari sau pentru digrafuri date printr-ofuncţie care returnează lista de adiacenţă a unui nod dat, implementărilefolosind matricea de cost-adiacenţă sunt fie ineficiente fie imposibile.O implementare care evită aceste lipsuri este dată pe slide-ul următor(Partition Shortest Path algoritm due to Glover, Klingman şi Philips(1985)).



Drumuri de cost minim - Algoritmul Partition Shortest Path (PSP)

Partition Shortest Path (PSP) algoritm

us 0; before(s) 0; S ?; NOW fsg; NEXT ?;while ( NOW [NEXT 6= ?) do

while (NOW 6= ?) doextrge i from NOW ; S S [ fig;L N+

G (i); //conţine adiacenţele şi costurile arcelor care pleacă din i .for (j 2 L) do

if (j =2 NOW [NEXT ) thenuj ui + aij ; before(j ) i ; insert j into NEXT ;

else if (uj > ui + aij ) thenuj ui + aij ; before(j ) i ;

if (NEXT 6= ?) thenfind d = min

i2NEXTui ; move to NOW each i 2 NEXT cu ui = d ;



Drumuri de cost minim - Problema P2 pentru costuri reale

Algoritmul Bellman-Ford-MooreDacă există un arc ij 2 E aşa încât aij < 0 atunci algoritmul lui Dijkstrapoate eşua (strategia "best first" nu mai funcţionează). Presupunând că

(I’) a(C ) > 0; 8C circuit în G ;

vom rezolva sistemul

(B)

(us = 0ui = minj 6=i (uj + aji ); 8i 6= s

prin aproximări succesive.




Algoritmul Bellman-Ford-MooreDefinim

(BM) uki = min fa(P) : P 2 Psi ; jE(P)j 6 kg; 8i 2 V ; k = 1;n � 1

Deoarece lungimea (numărul de arce) ale fiecărui drum din G este celmult n � 1, urmează că dacă vom construi

u1 = (u11 ; : : : ;u

1n);

u2 = (u21 ; : : : ;u

2n);

...un�1 = (un�1

1 ; : : : ;un�1n );

atunci un�1 este o soluţie a sistemului (B). Deoarece valorile lui u1 suntevidente, atunci, dacă vom indica o regulă de a trece de la uk la uk+1,vom obţine următorul algoritm pentru a rezolva (B):




Algoritmul Bellman-Ford-Mooreu1s 0;

for (i 2 V n fsg) dou1i asi ; //evident (BM) are loc.

for (k = 1;n � 2) dofor (i = 1;n) douk+1i min (uk

i ;minj 6=i (ukj + aji ));

Pentru a dovedi corectitudinea acestui algoritm, vom arăta că dacă uk

satisface (BM) atunci uk+1 satisface (BM), pentru k = 1;n � 2.




Algoritmul Bellman-Ford-Moore

(B)

(us = 0ui = minj 6=i (uj + aji );8i 6= s

Pentru i 2 V , considerăm următoarele mulţimi de drumuri:

A = fP : P 2 Psi ; length(P) 6 k + 1gB = fP : P 2 Psi ; length(P) 6 kgC = fP : P 2 Psi ; length(P) = k + 1g

Atunci, A = B [C , şi

min fa(P) : P 2 Ag = min (min fa(P) : P 2 Bg;min fa(P) : P 2 Cg)

Deoarece uki satisface (BM) avem

min fa(P) : P 2 Ag = min (uki ;min fa(P) : P 2 Cg)




Algoritmul Bellman-Ford-MooreFie min fa(P) : P 2 Cg = a(P0), pentru P0 2 C . Atunci j este noduldinaintea lui i 2 P0 (există un astfel de j deoarece P0 are cel puţin douăarce), atunci a(P0) = a(P0

sj ) + aji > ukj + aji (deoarece P0

sj are k arceşi uk satisface (BM). Astfel

min fa(P) : P 2 Ag = min (uki ;min

j 6=i(uk

j + aji ));

adică, valoarea asignată lui uk+1i în algoritm.

Complexitatea timp este O(n3) dacă minimul din al doilea for necesităO(n).Drumuri de cost minim pot fi obţinute ca şi în algoritmul lui Dijkstra,dacă vectorul before [], iniţializat trivial, este actualizat corespunzătoratunci când se determină minimul din cel de-al doilea for.




Remarci 4Algoritmul Bellman-Ford-Moore

Putem adăuga algoritmului următorul pas:

if (9i 2 V aşa încât un�1i > minj 6=i (un�1

j + aji )) thenreturn "există un circuit de cost negativ";

În acest fel se obţine un test de O(n3) dacă digraful G şi funcţia decost a încalcă condiţia (I’) (altfel, din demonstraţia corectitudinii,un�1i nu poate fi scăzut). Un circuit de cost negativ poate fi găsit

folosind vectorul before [].

Dacă există k < n � 1 aşa încât uk = uk+1 , atunci algoritmulpoate fi oprit. Folosind această idee, este posibil să implementămalgoritmul în O(nm), memorând nodurile i pentru care valoarea uise modifică în coadă.



Drumuri de cost minim - Rezolvarea problemei P3

P3 Dat G = (V ;E) digraf; a : E ! R:

Determină P�ij 2 Pij ;8i ; j 2 V ; a. î. a(P�

ij ) = min fa(Pij ) : Pij 2 Pij g

Fie uij = min fa(Pij ) : Pij 2 Pij g. Astfel avem de determinat ma-tricea U = (uij )n�n , când matricea de cost-adiacenţă A este dată.

Fiecare drum de cost minim poate fi obţinut în O(n) dacă, întimpul construcţiei matricei U , întreţinem matricea Before =

(beforeij )n�n , unde beforeij = nodul dinaintea lui j pe drumul decost minim de la i la j din G .

Dacă perechea (G ; a) satisface condiţia (I’), putem rezolva P3aplicând algoritmul Bellman-Ford-Moore pentru s 2 f1; : : : ;ng, înO(n4). Există şi soluţii mai eficiente pe care le vom prezenta peslide-urile următoare.




Iterarea algoritmului lui DijkstraDacă toate costurile sunt nenegative, putem rezolva P3 aplicând algo-ritmul lui Dijkstra pentru s 2 f1; : : : ;ng, în O(n3).Iterarea algoritmului lui Dijkstra este de asemeni posibilă si atunci cândavem costuri negative, dacă condiţia (I’) are loc, după o pre-procesareinteresantă.Fie � : V ! R aşa încât 8ij 2 E , �(i) + aij > �(j ).Fie a : E ! R+ dată prin a ij = aij + �(i)� �(j ), 8ij 2 E .Avem a ij > 0 şi nu este dificil de a vedea că pentru orice Pij 2 Pij ,

(*) a(Pij ) = a(Pij ) + [�(i)� �(j )]:

Astfel, putem itera algoritmul Dijkstra pentru a determina drumurile decost minim relativ la a .




Iterarea algoritmului lui DijkstraRelaţia (*) arată că un drum este de cost minim relativ la costul a dacăşi numai dacă este minim relativ la costul a (a(Pij ) � a(Pij ) este oconstantă care nu depinde de P). Astfel, avem următorul algoritm:1: find � and construct matrice A;2: solve P3 for A, returning U and Before ;3: find U (uij = u ij � �(i) + �(j ));

Pasul 2 necesită O(n3) din iterarea algoritmului lui Dijkstra. Pasul 1poate fi implementat în O(n3), alegând un nod s 2 V şi rezolvând P2cu algoritmul Bellman-Ford-Moore (care testează de asemeni dacă (I’)este îndeplinită).




Iterarea algoritmului lui DijkstraÎntr-adevăr, dacă (ui ; i 2 V ) este soluţie pentru P2, atunci (ui ; i 2 V )

satisface sistemul (B), deci uj = mini 6=j

(ui + aij ), adică, 8ij 2 E , avem

uj 6 ui + aij . Astfel, aij + ui � uj > 0, 8ij 2 E , ceea ce arată că putemlua �(i) = ui , 8i 2 V aşa încât condiţia (*) să aibă loc.

Algoritmul Floyd - WarshallFie

ukij = min fa(Pij : Pij 2 Pij ;V (Pij ) n fi ; j g � f1; 2; : : : ; k � 1gg

8i ; j 2 V ; k = 1;n + 1:




Algoritmul Floyd - WarshallEvident, u1

ij = aij , 8i ; j 2 V (presupunem că aii = 0, 8i 2 V ). Maimult,

uk+1ij = min fuk

ij ;ukik + uk

kj g; 8i ; j 2 V ; k = 1;n :

Aceasta rezultă prin inducţie după k . În pasul inductiv: un drum decost minim de la i la j fără noduri interne > k+1 fie nu conţine nodul kşi costul său este uk

ij , fie conţine nodul k şi atunci costul său este ukik+uk

kj(din principiul de optimalitate al lui Bellman şi ipoteza inductivă).Evident, dacă obţinem uk

ii < 0, atunci există un circuit de cost negativC care trece prin nodul i cu V (C ) n fig � f1; : : : ; k � 1g.




for (i = 1;n) dofor (j = 1;n ) dobefore(i ; j ) i ;if (i = j ) thenaii 0; before(i ; i) 0;

for (k = 1;n ) dofor (i = 1;n) do

for (j = 1;n ) doif (aij > aik + akj ) thenaij aik + akj ; before(i ; j ) before(k ; j );if (i = j şi aij < 0) thenreturn "circuit negativ";




Această metodă pentru rezolvarea problemei P3 este cunoscută dreptalgoritmul Floyd - Warshal:Evident, complexitatea timp a acestui algoritm este O(n3).

RemarcăDacă ştim că digraful nu are circuite de cost negative, atunci dacă el-ementele diagonale ale lui A sunt iniţializate cu 1, valoarea finală afiecărui element diagonal este costul minim al unui circuit care treceprin nodul corespunzător.




Înmulţirea (rapidă) a matricilorSă presupunem că (I’) este îndeplinită şi în matricea de cost-adiacenţăelementele diagonale sunt 0. Fie

ukij = min fa(Pij ) : Pij 2 Pij ;Pij are cel mult k arceg

8i ; j 2 V ; k = 1;n � 1:

Notăm cu U k = (ukij )16i ;j6n pentru k 2 f0; 1; 2; : : : ;n�1g, unde U 0 are

toate elementele1, mai puţin cele de pe diagonal ă care sunt 0. Atunci,iterarea algoritmului Bellman-Ford-Moore poate fi descrisă într-o formămatriceală:




Înmulţirea (rapidă) a matricilorfor (i ; j 2 V ) do

if (i 6= j ) thenu0ij 1;

elseu0ij 0;

for (k = 0;n � 2 ) dofor (i ; j 2 V ) douk+1ij = min

h2V(uk

ih + ahj );




Înmulţirea (rapidă) a matricilorConsiderăm următorul “produs de matrici”

8B ;C 2Mn�n ;B C = P = (pij ); where pij = mink=1;n

(aik + bkj ):

Operaţia este asociativă şi este similară înmulţirii uzuale a matricilor.Putem scrie Um+1 = Um A şi, prin inducţie, obţinem

U 1 = A;U 2 = A(2); : : : ;U n�1 = A(n�1);

where A(k) = A(k�1) A şi A(1) = A:

În ipoteza (I’) avem: A(2p) = A(n�1), 8p cu 2p > n � 1.Astfel, calculând succesiv, A;A(2);A(4) = A(2) A(2); : : :,obţinem al-goritm cu O(n3 logn) complexitate timp pentru rezolvarea problemeiP3.




Remarcă 1Dacă operaţia este implementată cu algoritmi mai rapizi, n3 de maisus devine n log2 7 = n2:81 (Strassen 1969) sau n2:3728639 (Cooppersmith& Winograd 1987, Le Gall 2014).



Exerciţii pentru seminarul de săptămâna următare

Exerciţiul 1’. Rulaţi algoritmul lui Dijkstra pe digraful următor.




Exerciţiul 1. Un graf G este dat funcţional: pentru fiecare nod v 2V (G) putem obţine NG(v) pentru 1$; alternativ, după o preprocesarecare costă T$ (T >> 1), putem obţine, NG(v) şi also NG(w), pentrutoate nodurile w 2 V (G). În G se construieşte un drum P plecânddintr-un nod arbitrar şi alegând un vecin nevizitat încă atâta vremecât este posibil. După ce drumul este construit putem să îi comparămcostul, Online(P), cu cel mai mic cost posibil, Offline(P). Descrieţi ostrategie de plată (de accesare a mulţimilor de vecini) aşa încât

Online(P) 6

�2�

1T

��Offline(P):




Exerciţiul 2. Fie D un digraf şi a : E(D) ! R+, b : E(D) ! R�+.

Descrieţi algoritm eficient pentru determinarea unui circuit C � of D ,aşa încât

a(C �)

b(C �)= min

�a(C )

b(C ): C circuit în D

�:

Exerciţiul 3. În problema determinării drumurilor de cost minim dela un nod dat s la toate celelalte noduri dintr-un digraf G = (V ;E),avem o funcţie de cost c : E ! f0; 1; : : : ;Cg unde C 2 N nu depinde den = jV j sau de m = jE j. Cum se poate modifica algoritmul lui Dijkstrapentru a reduce complexitatea timp la O(n +m)?




Exerciţiul 4. Fie D = (V ;E) un digraf tare conex de ordin n şia : E ! R o funcţie de cost pe arcele sale. Dacă X este un mers,un drum sau un circuit în D , atunci a(X ), costul lui X , este sumacosturilor de pe arcele sale, len(X ), este lungimea lui X (numărul de

arce), şi aavg(X ), costul mediu al arcelor sale, este aavg(X ) =a(X )

len(X ).

Fiea�avg = min

C circuit în Daavg(C ):

Fie s 2 V , k 2 N�, şi Ak (v) costul minim al unui mers de la s la v delungime k (dacă există un astfel de mers, altfel Ak (v) = +1).




Exerciţiul 4. (cont’d)

a) Dacă D nu conţine circuite de cost negativ, dar există un circuit Ccu a(C ) = 0, arătaţi că există un nod v 2 V aşa încât

An(v) = min fa(P) : P este un sv -drum de la s la v in Dg:

b) Arătaţi că dacă a�avg = 0, atunci

(MMC ) a�avg = minv2V

max06k6n�1

An(v)�Ak (v)n � k

:

c) Dacă a�avg 6= 0, transformaţi funcţia a aşa încât noua funcţie a 0 săsatisfacă ipoteza de la b) şi din (MMC ) (care are loc pentru a 0)arătaţi că (MMC ) are loc pentru orice funcţie a .




Exerciţiul 5. În numeroase aplicaţii, pentru un digraf dat, G = (V ;E)

cu a : E ! R+, trebuie să răspundem consecvent la o întrebare de tipulurmător: Care este drumul de cost minim dintre s şi t? (s ; t 2 V ,s 6= t). Pentru un digraf foarte mare, G , se propune următorul algoritmDijkstra modificat (bidirecţional):

construieşte inversul lui G , G 0, cu funcţia de cost a 0 : E(G 0)! R+,dată prin a 0ij = aji , 8ij 2 E(G 0);

aplică succesiv un pas din algoritmul lui Dijkstra luiG şi a (plecânddin s) şi lui G 0 şi a 0 (plecând din t);

când un nod u este introdus în S (mulţimea nodurilor etichetatede algoritmul lui Dijkstra) de amândouă instanţele algoritmului neoprim;

returnează drumul de la s la u în G reunit cu inversul drumului dela t la u în G 0.

Arătaţi că această procedură nu este corectă, oferind un exemplu caresă fie inconsistent cu ea. Algoritmica grafurilor - Cursul 4 25 octombrie 2019 41 / 44



Exerciţiul 6. Daţi un exemplu de digraf care să aibă şi costuri negativepe arce şi pe care algoritmul lui Dijkstra să eşueze.

Exerciţiul 7. Fie G un graf conex. Arătaţi că

a) orice două drumuri de lungime maximă ale lui G au intersecţienevidă.

b) dacă G este un arbore, atunci toate drumurile de lungime maximădin G au intersecţia nevidă.

Exerciţiul 8. Fie G = (V ;E) un graf conex.

a) Arătaţi că există o mulţime stabilă, S , aşa încât graful parţial bi-

partit H = (S ;V n S ;E 0) să fie conex, unde E 0 = E n

V n S

2

!.

(b) Arătaţi că �(G) >jG j � 1�(G)

.Algoritmica grafurilor - Cursul 4 25 octombrie 2019 42 / 44



Exerciţiul 9. Arătaţi că orice arbore, T , are cel puţin �(T ) noduripendante (frunze).

Exerciţiul 10. Fie G un graf cu n > 2 noduri şi m muchii.

a) Arătaţi că G conţine cel puţin două noduri de acelaşi grad.

b) Fie r(G) numărul maxim de noduri având acelaşi grad în G . Dacănotăm cu dmed = 2m=n , demonstraţi că

r(G) >

�n

2dmed � 2�(G) + 1

�:




Exerciţiul 11. Fie G = (S ;T ;E) un graf bipartit cu următoareleproprietăţi:

- jS j = n ; jT j = m (n ;m 2 N�);

- 8t 2 T ; jNG(t)j > k > 0 (pentru un k < n fixat);

- 8t1; t2 2 T , dacă t1 6= t2, atunci jNG(t1) \NG(t2)j = k ;

Arătaţi că m 6 n ;

Exerciţiul 12. Fie G = (V ;E) un digraf; definim o funcţie fG :

P(V ) ! N prin fG(?) = 0 şi fG(S) = jfv : v este accesibil din Sgj,pentru ? 6= S � V .

(a) Arătaţi că, pentru orice digraf G, avem

fG(S) + fG(T ) > fG(S [T ) + fG(S \T ); 8 S ;T � V :

(b) Demonstraţi că (a) este echivalentă cu

fG(X[fvg)�fG(X ) > fG(Y[fvg)�fG(Y );8X � Y � V ;8v 2 V nY :Algoritmica grafurilor - Cursul 4 25 octombrie 2019 44 / 44

Algoritmicagrafurilor-Cursul4olariu/curent/AG/files/agr4.pdf · G = ( V; E) este un digraf fără...

Documents

Transcript of Algoritmicagrafurilor-Cursul4olariu/curent/AG/files/agr4.pdf · G = ( V; E) este un digraf fără...