STRUCURA DE DATE DE TIP GRAF

STRUCURA DE DATE DE TIP GRAF

Aspecte generale

Lucrarea de fata este structurata in patru capitole si contine o prezentare a metodelor de traversare a grafurilor.Cele patru capitole au urmatoarea structura:

Capitolul I - O scurta prezentare a notiunii de graf: definitii,exemple si tot aici sunt prezentate si cateva domenii de activitate in care sunt utilizate grafurile, de aici rezultand si importanta utilizarii acestora.

Capitolul II - In acest capitol sunt prezentate metodele de implementare a grafurilor si anume:

metoda de implementare a grafurilor prin matrice de adiacenta

metoda de implementare a grafurilor prin structuri de adiacente

Capitolul III - Contine o prezentare detaliata a metodelor de traversare a grafurilor neorientate:

Tehnica de traversare bazata pe cautarea prin cuprindere (Breadth-First Search)

Tehnica de traversare bazata pe cautarea in adancime (Depth-First Search)

Capitolul IV - Prezentarea aplicatiei GraphSearch

In problemele care apar in programare, matematica, inginerie si in multe alte domenii, apare deseori necesitatea reprezentarii unor relatii arbitrare intre diferite obiecte, respectiv a interconexiunilor dintre acestea.Spre exemplu, dandu-se traseele aeriene ale unui stat se cere sa se precizeze drumul optim dintre doua orase.Criteriul de optimalitate poate fi timpul sau pretul, drumul optim putand sa difere pentru cele doua situatii.Pentru rezolvarea unei astfel de probleme sunt necesare informatii referitoare la interconexiunile (traseele aeriene) dintre obiecte (orase).

Circuitele electrice sunt alte exemple evidente in care interconexiunile dintre obiecte joaca un rol central. Piesele (tranzistoare, rezistente, condensatoare) sunt interconectate prin fire electrice.Astfel de circuite pot fi reprezentate si prelucrate de catre un sistem de calcul in scopul rezolvarii unor probleme simple, cum ar fi: "sunt toate piesele date, conectate in acelasi circuit?", sau a unor probleme mai complicate cum ar fi: "este functional un anumit circuit electric?". Raspunsul la prima intrebare poate fi determinat simplu, el depinzand numai de elementele de interconectare (fire), in timp ce al doilea raspuns necesita informatii detaliate atat asupra interconexiunilor, cat si asupra pieselor implicate.

Un al treilea exemplu il reprezinta planificarea activitatilor, in care obiectele sunt task-uri (activitati,procese), iar interconexiunile precizeaza care dintre activitati trebuie finalizate inaintea altora. Ele trebuie sa ofere raspuns intrebarii "cand va fi executata fiecare activitate?

Structurile de date care pot modela in mod natural situatii de natura celor de mai sus prezentate sunt cele derivate din obiectul matematic cunoscut sub denumirea de graf.

Teoria grafurilor este o ramura majora a matematicii combinatorii care in timp a fost intens studiata.

Ca si in alte domenii, studiul algorithmic al grafurilor, respectiv al structurilor de date de tip graf, este de data relativ recenta astfel incat alaturi de algoritmii fundamentali cunoscuti de mai multa vreme, multi dintre algoritmii de mare interes au fost descoperiti in ultimii ani.

2.Definitii si exemple de grafuri

2.Graf,arce,ordinul unui graf,gradul unui graf

Un graf este alcatuit din o multime de noduri (sau varfuri) si o multime de arce (sau muchii). Fiecare arc din graf este specificat de o pereche de noduri. Figura 1(a) ilustreaza un graf. Multimea de noduri este , iar multimea de arce este . Daca perechile de noduri ce alcatuiesc arcele sunt perechi ordonate, atunci se spune ca graful este orientat sau digraf (directed graph). Figurile 1(b),1(c) si 1(d) ilustreaza trei grafuri orientate.

Figura 1 Exemple de grafuri

Sagetile dintre noduri reprezinta arce.Varful fiecarei sageti reprezinta al doilea nod in perechea ordonata de noduri ce constituie un arc, iar coada fiecarei sageti reprezinta primul nod in pereche. Deci in cadrul grafurilor orientate, arcele sunt orientate, avand un sens precizat de la x la y spre exemplu si nu de la y la x. In acest caz x se numeste coada sau sursa arcului, iar y varful sau destinatia sa. Pentru reprezentarea acestor arce se utilizeaza sageti sau segmente directionate. Multimea de arce din figura 1(b) este:.Folosim paranteze rotunde pentru a indica o pereche neordonata si paranteze ascutite pentru a indica o pereche ordonata. Exista si cazuri cand un nod nu are arce asociate, de exemplu nodul H din figurile 1(a) si 1(b).

Notand cu N multimea nodurilor si cu A multimea arcelor, un graf poate fi notat si in forma G=(N,A).

Ordinul unui graf este numarul de noduri pe care acesta le contine si se noteaza cu | G |. Arcele definesc o relatie de incidenta intre perechile de noduri. Doua noduri conectate printr-un arc se numesc adiacente, altfel ele sunt independente.Daca a este un arc care leaga nodurile x si y (a~(x,y)), atunci a este incident cu x,y. Singura proprietate presupusa pentru aceasta relatie este simetria.

Un arc poate fi definit astfel incat sa aiba un arc a~(x,x).Un astfel de arc se numeste bucla (loop). Daca relatia de incidenta este reflexiva, atunci fiecare nod contine o astfel de bucla. Exista posibilitatea sa fie mai multe arce care conecteaza aceeasi pereche de noduri. In figura 2 este reprezentat un graf cu bucla si arc multiplu.Grafurile in care nu sunt acceptate arce multiple se numesc simple.

Figura2 - Graf cu arc multiplu si bucla

Gradul unui nod este numarul de arce incidente la acel nod.Intr-un graf orientat,gradul pozitiv (indegree) al unui nod este numarul de arce ce au acel nod ca varf, iar gradul negativ (outdegree) al unui nod este numarul de arce ce au acel nod ca si coada.De exemplu, nodul A in figura 1(d) are gradul pozitiv 1,iar gradul negativ 2.Intr-un graf orientat un nod n este adiacent la un nod m daca exista un arc de la m la n.Daca n este adiacent la m,n se numeste succesorul lui m,iar m predecesorul lui n.

Un graf de ordinul n este complet daca fiecare pereche de noduri este adiacenta.Un graf complet de ordinul n il vom nota Kn (figura 3).

Figura 3 - Grafuri complete

2.2.Graf planar,graf bipartit,graf valoric

Un graf se numeste planar daca el poate fi reprezentat intr-un plan astfel incat oricare doua arce ale sale sa se intersecteze doar in noduri.O teorema demonstrata de Kuratowski precizeaza ca orice graf neplanar contine cel putin unul din urmatoarele grafuri de baza:

- un graf complet (de exemplu graful K5 din figura 3) sau

graful utilitar in care exista doua multimi de cate trei noduri, fiecare nod dintr-o multime fiind legat de toate nodurile din cealalta multime (exemplu figura 4)

Figura 4 - Graf utilitar

Un graf se numeste bipartit daca nodurile sale pot fi partitionate in doua multimi distincte N1 si N2 astfel incat orice arc al sau conecteaza un nod din N1 cu un nod din N2.

Fie G N,A) un graf cu multimea nodurilor N si cu multimea arcelor A.Un subgraf al lui G este graful G'=(N',A') unde:

- N' este o submultime a lui N

A' consta din arce (x,y) ale lui A,astfel incat x si y apartin lui N'.

(a) (b)

Figura5(a) - Graf Figura 5(b) - Subgraf

Daca A' contine toate arcele (x,y) ale lui A pentru care atat x cat si y sunt in N', atunci G' se numeste subgraf indus al lui G.

O relatie R a unei multimi A este o multime de perechi ordonate a elementelor lui A. De exemplu daca A=, multimea R= este o relatie.Daca <x,y> este un membru al relatiei R, x se spune ca este in relatia R cu y.Relatia R de mai sus poate fi descrisa spunand ca x este in relatie cu y daca x este mai mic decat y si restul obtinut prin impartirea lui y la x este impar. <8,17> este un membru al relatiei, intrucat 8 este mai mic decat 17 si restul impartirii lui 17 la 8 este 1, care este impar. O relatie poate fi reprezentata de un graf, unde nodurile reprezinta multimea de baza, iar arcele reprezinta perechile ordonate ale relatiei. Figura 6(a) ilustreaza graful reprezentat de relatia de mai sus.

Figura6 - Relatii si grafuri

Un graf in care fiecarui arc ii este asociat un numar, se numeste graf valoric(weighted graph), graf ponderat sau retea (network). Numarul asociat arcului se numeste valoare (weight).Un astfel de graf este ilustrat in figura 6(b).

In continuare sunt prezentate cateva operatii primitive care sunt folositoare in lucrul cu grafuri:

-functia adauga(x,y) adauga un arc de la nodul x la nodul y daca acesta nu exista inca;

adaugaV(x,y,v) aduga un arc de la nodul x la nodul y de valoare v in graful valoric;

2-functia sterge(x,y) sterge un arc de la nodul x la nodul y daca exista arcul respectiv;

StergeV(x,y,v) sterge un arc de la nodul x la y de valoare v in graful valoric, daca exista arcul respectiv;

3.-functia adiacent(x,y) returneaza TRUE daca y este adiacent cu x si FALSE in caz contrar.

2.3.Drum simplu sau elementar, ciclu, ciclu elementar, graf conex,

graf ciclic, ciclu Hamiltonian, graf Hamiltonian, ciclu eulerian,

graf eulerian

Definitie: Un drum de lungime k de la nodul x la nodul y este definit ca o secventa de k+1 noduri:n1,n2,.,nk+1 astfel incat n1=x, nk+1=y si adiacent(ni,ni+1) este adevarat pentru i =1.k. Lungimea drumului este, deci, egala cu numarul de arce ale drumului. Un drum se numeste simplu sau elementar daca toate nodurile sale, exceptand eventual primul si ultimul, sunt diferite doua cate doua.

Definitie: Un ciclu (bucla) este un drum de lungime cel putin 1, care incepe si se sfarseste cu acelasi nod si care are toate arcele distincte.

De exemplu drumul A F E G A din figura 7 este un ciclu.

Figura 7 - Exemple de drumuri

Definitie: Se numeste ciclu elementar un ciclu care are proprietatea ca oricare doua varfuri ale sale, cu exceptia primului si a ultimului nod, sunt diferite doua cate doua.

Un graf se numeste ciclic daca contine cel putin un ciclu.

Definitie: Intr-un graf G N,A), un ciclu elementar care contine toate varfurile grafului se numeste ciclu Hamiltonian.

Definitie: Se numeste graf hamiltonian un graf care contine un ciclu Hamiltonian.

Figura 8 - Graf hamiltonian

Definitie: Fie un graf G N,A). Se numeste ciclu eulerian un ciclu care contine toate muchiile grafului.Un graf care contine un ciclu eulerian se numeste graf eulerian.

Graful din figura 9 este eulerian deoarece el contine ciclul eulerian A J B C D E F C G H J I M K J L A.

Figura 9 - Graf eulerian

Un graf se numeste conex daca de la fiecare nod al sau exista un drum spre oricare alt nod al grafului, respectiv daca oricare pereche de noduri apartinand grafului este conectata.

Un graf conex aciclic se mai numeste si arbore liber. In figura 10 apare un graf constand din doua componente conexe, in care fiecare componenta este un arbore liber.

Figura 10 - Graf neorientat, cu componente conexe

Se remarca in acest sens observatia ca arborii sunt cazuri particulare ale grafurilor.Un grup de arbori neconectati formeaza o padure (forest).

Notand cu n numarul de noduri ale unui graf si cu a numarul de arce, atunci a poate lua orice valoare intre 0 si n(n-1)/2

Graful care contine toate arcele posibile este graful complet de ordinul n (Kn), graful care are relativ putine arce (de exemplu a<n log n) se numeste graf rar (sparse), iar graful cu un numar de arce apropiat de graful complet se numeste graf dens.