Grafurile orientate
Grafurile orientate sunt grafuri în care arcele care conectează nodurile au un singur sens. Această restricţie face mult mai dificilă evidenţierea şi exploatarea diverselor proprietăţi ale grafurilor de acest tip. Prelucrarea unui astfel de graf este identică cu o călătorie cu maşina într-un oraş cu foarte multe străzi cu sens unic sau cu o călătorie cu avionul într-o ţară în care liniile aeriene nu sunt dus-întors. În astfel de situaţii a ajunge dintr-un loc în altul poate reprezenta o adevărată problemă.
De multe ori arcele orientate reflectă anumite tipuri de relaţii de precedenţă în aplicaţia pe care o modelează.
Spre exemplu un graf orientat poate fi utilizat ca model pentru o linie de fabricaţie:
Nodurile corespund diverselor operaţii care trebuiesc executate.
Un arc de la nodul x la nodul y precizează faptul că operaţiunea corespunzătoare nodului x trebuie executată înaintea celei corespunzătoare nodului y.
În acest context, problema care se pune este aceea de a executa toate aceste operaţii, fără a eluda niciuna dintre relaţiile de precedenţă impuse.
După cum s-a menţionat în capitolul 10, reprezentările grafurilor orientate sunt simple extensii (de fapt restricţii) ale reprezentărilor grafurilor neorientate. Astfel:
- În reprezentarea bazată pe liste de adiacenţe, fiecare arc apare o singură dată: arcul de la nodul x la y este reprezentat prin prezenţa nodului y în lista de adiacenţe a lui x. - În reprezentarea bazată pe matrice de adiacenţe, arcul de la nodul x la y se marchează tot o singură dată, prin valoarea "adevărat" a elementului matricii de adiacenţe situat în linia x, coloana y (nu şi a elementului situat în linia y, coloana x). În figura 12.1.a apare un exemplu de graf orientat: -Graful constă din arcele AG,AB,CA,LM,JM,JL,JK,ED,DF,NI,FE,AF,GE,GC,HG,GJ,LG,IH, ML. -Ordinea în care nodurile apar la specificarea arcelor este semnificativă. -Notaţia AG precizând un arc care îşi are sursa în nodul Aşi destinaţiaîn nodul G. -Este însă posibil ca întredouănoduri să două arce având sensuri opuse (exemplu HI şi IH, respectiv LM şi ML).
fig.12.1. Pornind de la această precizare este uşor de observat faptul că un graf neorientat poate fi asimilat cu graful orientat identic ca şi structură, care conţine pentru fiecare arc al grafului neorientat două arce opuse.
În acest context unii dintre algoritmii dezvoltaţi în acest capitol, pot fi consideraţi generalizări ale algoritmilor din capitolele anterioare.
În cadrul acestui capitol vor fi prezentate unele dintre problemele specifice acestei categorii de grafuri precum şi o serie de algoritmi consacraţi care le soluţionează. Este vorba despre: (1) Problema drumurilor minime cu origine unică (2) Problema drumurilor minime corespunzătoare tuturor perechilor de noduri (3) Închiderea tranzitivă (4) Grafuri orientate aciclice (5) Componente conectate în grafuri orientate
Problema drumurilor minime cu origine unica
O primă problemă care se abordează în contextul grafurilor orientate este următoarea: Se consideră un graf orientat G=(N,A) în care fiecare arc are o pondere pozitivă şi pentru care se precizează un nod pe post de “origine”. Se cere să se determine costul celui mai scurt drum de la origine la oricare alt nod al grafului Conform celor deja precizate, costul unui drum este suma ponderilor arcelor care formează drumul. Această problemă este cunoscută sub numele de problema drumurilor minime cu origine unică (“single source shortest path problem”). Desigur o abordare mai naturală, ar fi aceea care-şi propune să determine cel mai scurt drum de la o origine la o destinaţie precizată. Această problemă are acelaşi grad de dificultate ca şi problema anterioară care de fapt o generalizează. Astfel, pentru a rezolva această ultimă problemă, este suficient ca execuţia algoritmului care determină drumurile minime cu origine unică să fie oprită în momentul în care se ajunge la destinaţia precizată. Exact ca şi în cazul grafurilor ponderate neorientate, ponderea poate avea semnificaţia fizică a unui cost, a unei valori, a unei lungimi, a unui timp, etc. Intuitiv, graful G poate fi asimilat cu o hartă a traseelor aeriene ale unui stat în care: Fiecare nod reprezintă un oraş Fiecare arc (x,y) reprezintă o legătură aeriană de la oraşul x la oraşul y. Ponderea unui arc (x,y) poate fi timpul de zbor sau preţul biletului. Desigur, ca model ar putea fi utilizat şi un graf neorientat deoarece ponderea arcului (x,y) trebuie să fie în principiu aceeaşi cu cea a arcului (y,x). În realitate pe de o parte nu toate traseele aeriene sunt dus-întors, iar pe de altă parte dacă ele sunt dus-întors, timpul de zbor s-ar putea să difere în cele două sensuri. În orice caz, considerând arcele (x,y) şi (y,x) cu ponderi identice, aceasta nu conduce la o simplificare a rezolvării problemei. Pentru a rezolva problema drumurilor minime cu origine unică, o manieră clasică de abordare o reprezintă utilizarea unui algoritm bazat pe tehnica “greedy” adesea cunoscut sub denumirea de “algoritmul lui Dijkstra”Acest algoritm a fost publicat de către E.W. Dijkstra în anul 1959. Algoritmul se bazează pe o structură de date mulţime M care conţine nodurile pentru care cea mai scurtă distanţă la nodul origine este deja cunoscută. Iniţial M conţine numai nodul origine. În fiecare pas al execuţiei algoritmului, se adaugă mulţimii M un nod x care nu aparţine încă mulţimii şi a cărui distanţă de la origine este cât mai scurtă posibil. Presupunând că toate arcele au ponderi pozitive, întotdeauna se poate găsi un drum minim care leagă originea de nodul x, drum care trece numai prin nodurile conţinute de M. Un astfel de drum se numeşte “drum special”. Pentru înregistrarea lungimii drumurilor speciale corespunzătoare nodurilor grafului se utilizează un tablou D care este actualizat în fiecare pas al algoritmului. În momentul în care M include toate nodurile grafului, toate drumurile sunt speciale şi în conscinţă, tabloul D memorează cea mai scurtă distanţă de la origine la fiecare nod al grafului.Schiţa de principiu a algoritmului lui Dijkstra apare în secvenţa [12.1.1.a]------------------------------------------------------------PROCEDURE Dijkstra; {Determină costurile celor mai scurte drumuri care conectează nodul 1, considerat drept origine, cu toate celelalte noduri ale unui graf orientat}
BEGIN
[1] M:= [1]; {nodul origine}
[2] FOR i:= 2 TO n DO {iniţilizarea lui D}
[3] D[i]:= COST[1,i]; [12.1.1.a]
[4] FOR i:= 1 TO n-1 DO
BEGIN
[5] *alege un nod x aparţinând mulţimii N - M astfel încât D[x] să fie minim;
[6] *adaugă pe x lui M;
[7] FOR fiecare nod y din N - M DO [8] D[y]:= min(D[y],D[x] + COST[x,y])
END
END; {Dijkstra} ------------------------------------------------------------
- Referitor la algoritmul lui Dijkstra, se presupune că:
- Se dă un graf orientat G= (N,A) unde N={1,2,3,…,n}
- Nodul 1 este considerat drept origine.
- COST este un tablou cu două dimensiuni unde COST[i,j] reprezintă costul deplasării de la nodul i la nodul j pe arcul (i,j).
- Dacă arcul (i,j) nu există, se presupune că C[i,j] este ∞, respectiv are o valoare mai mare decât orice cost.
- La fiecare iteraţie a algoritmului, tabloul D[i] conţine lungimea drumului special minim curent de la origine la nodul i.
Iniţia lM={1},D[2]=10,D[3]=∞,D[4]=30şiD[5]=100. În continuare se faceD[3]=min(∞,10+50)=60. D[4] şi D[5]nu se modifică deoarece în ambele cazuri, drumuldirect care conectează nodurile respective cu originea este mai scurt decât drumul care trece prin nodul 2.În continuare, modul în care se modifică tabloul D după fiecare iteraţie a buclei FOR mai sus precizate apare în figura 12.1.1.b.
Fig.12.1.1.b.Determinarea drumurilor minime cu origine unică în baza algoritmului lui Dijkstra.În vederea reconstrucţiei drumurilor minime de la origine la fiecare nod al grafului, se utilizează un alt tablou Părinte În acest tablou, Părinte[x] memorează nodul care precede nodul x în cadrul drumului minim, adică memorează tatăl nodului x. Tabloul Părinte se iniţializează cu Părinte[i]=1 pentru toate valorile lui i≠1. Tabloul Părinte poate fi actualizat după linia [8] în procedura Dijkstra din secvenţa [12.1.1.a]. Astfel, dacă în linia [8], D[x]+COST[x,y]<D[y], atunci se face Părinte[y]:=x. După terminarea procedurii, drumul la fiecare nod poate fi reconstituit în sens invers mergând pe înlănţuirile indicate de tabloul Părinte. Astfel, pentru graful orientat din fig. 12.1.1.a, tabloul Părinte conţine valorile precizate în figura 12.1.1.b. Pentru a găsi spre exemplu, drumul minim de la nodul 1 la nodul 5 al grafului, se determină predecesorii (părinţii) în ordine inversă începând cu nodul 5. Astfel se determină 3 ca predecesorul lui 5, 4 ca predecesor al lui 3, 1 ca predecesor al lui 4. În consecinţă drumul cel mai scurt de la nodul 1 la nodul 5 este 1,4,3,5 iar lungimea sa 60 este memorată în D[5]. Se presupune că algoritmul din secvenţa [12.1.1.a], operează asupra unui graf orientat cu n noduri şi a arce. Dacă pentru reprezentarea grafului se utilizează o matrice de adiacenţe, atunci bucla FOR din liniile [7]-[8] necesită un efort de calcul proporţional cu O(n). Întrucât această buclă este executată de n-1 ori, (bucla FOR din linia [4]), timpul total de execuţie va fi proporţional cu O(n2). Este uşor de observat că restul algoritmului nu necesită timpi superiori acestei valori. (2) Dacă a este mult mai mic decât n2, este mai indicat ca în reprezentarea grafului să se utilizeze liste de adiacenţe, respectiv o coadă bazată pe prioritate implementată ca un ansamblu (arbore binar parţial ordonat), pentru a păstra distanţele la nodurile mulţimii N-M. În aceste condiţii, bucla din liniile [7]-[8] poate fi implementată ca şi o traversare a listei de adiacenţa a lui x cu actualizarea distanţelor nodurilor din coada bazată pe prioritate. În total, pe întreaga durată a execuţiei procedurii, se vor realiza a actualizării, fiecare cu un efort proporţional cu O(log n), astfel încât timpul total consumat în liniile [7]-[8] va fi proporţional cu O(a log n) şi nu cu O(n2). În mod evident liniile [2]-[3] necesită asemeni liniilor [4]-[6] un efort de calcul proporţional cu O(n). Utilizând în reprezentarea mulţimii N-M o coadă bazată pe priorităţi, linia [5] implementează operaţia de extragere a elementului cu prioritatea minimă din coadă, fiecare din cele n-1 iteraţii ale acestei linii necesitând O(log n) unităţi de timp. În consecinţă, timpul total consumat de această variantă a algoritmului lui Dijkstra este limitat la O(a log n) (a≥n-1), performaţă care este considerabil mai bună decât O(n2). Se reaminteşte faptul că această performanţă se poate obţine numai dacă a este mult mai mic în raport cu n2.
Algoritmul lui Dijkstra
În prima iteraţie a buclei FOR din liniile [4]–[8], se selectează x=2 ca fiind
nodul de distanţă minimă din D.
În continuare se face D[3]=min(∞,10+50)=60.
D[4] şi D[5] nu se modifică deoarece în ambele cazuri, drumul
direct care conectează nodurile respective cu originea este mai scurt
decât drumul care trece prin nodul 2.
În continuare, modul în care se modifică tabloul D după fiecare iteraţie a
buclei FOR mai sus precizate apare în figura 12.1.1.b.
Iteratia M x D[2] D[3] D[4] D[5]
Initial {1} - 10 ∞ 30 100
(1) {1,2} 2 10 60 30 100
(2) {1,2,4} 4 10 50 30 90
(3) {1,2,4,3} 3 10 50 30 60
(4) {1,2,4,3,5} 5 10 50 30 60
x 1 2 3 4 5
Parinte[x] 0 1 4 1 3
1
4
3
2
5
Fig.12.1.1.b. Determinarea drumurilor minime cu origine unică în baza algoritmului lui
Dijkstra
În vederea reconstrucţiei drumurilor minime de la origine la fiecare nod al grafului, se utilizează un alt tablou Părinte
În acest tablou, Părinte[x] memorează nodul care precede nodul x în cadrul drumului minim, adică memorează tatăl nodului x.
Tabloul Părinte se iniţializează cu Părinte[i]=1 pentru toate valorile lui i≠1.
Tabloul Părinte poate fi actualizat după linia [8] în procedura Dijkstra din secvenţa [12.1.1.a].
Astfel, dacă în linia [8], D[x]+COST[x,y]<D[y], atunci se face Părinte[y]:=x.
După terminarea procedurii, drumul la fiecare nod poate fi reconstituit în sens invers mergând pe înlănţuirile indicate de tabloul Părinte.
Astfel, pentru graful orientat din fig. 12.1.1.a, tabloul Părinte conţine valorile precizate în figura 12.1.1.b.
Pentru a găsi spre exemplu, drumul minim de la nodul 1 la nodul 5 al grafului,
se determină predecesorii (părinţii) în ordine inversă începând cu nodul 5.
Astfel se determină 3 ca predecesorul lui 5, 4 ca predecesor al lui 3, 1 ca predecesor al lui 4.
În consecinţă drumul cel mai scurt de la nodul 1 la nodul 5 este 1,4,3,5 iar lungimea sa 60 este memorată în D[5].
În aceeaşi figură apare reprezentat şi arborele de acoperire corespunzător drumurilor minime cu origine unică ataşat grafului din figura 12.1.1.a.
Niciun comentariu:
Trimiteți un comentariu