GRAFUL

Graful

Graful este se defineste ca fiind perechea G=(V,R),unde V este multimea nodurilor sau varfurilor, iar elementele multimii R se numesc muchii. Muchiile sunt perechi (v,w) din multimea VxV. Grafurile modeleaza relatii simetrice dintre obiecte simetrice dintre obiecte. Exemple de grafuri : harta cailor ferate dintr-o tara, harta care infatiseaza reteaua drumurilor cu doua sensuri de mers dintr-un oras, schema instalatiei de curent electric dintr-o institutie etc.

Un caz particular important al grafului este graful orientat sau digraful (notiunea de digraf vine de la directed graph). Digraful modeleaza relatii nesimetrice dintre obiecte.

De exemplu, se poate vorbi despre digraful datoriilor dintre membrii unui grup de persoane, despre digraful simpatiilor unui astfel de grup sau despre digraful care reprezinta o retea de comunicatii etc.. Matematic, un digraf se defineste ca fiind perechea G=(V,E), unde V este multimea nodurilor sau varfurilor, iar elementele multimii E se numesc arce. Arcele sunt perechi (v,w) din VxV : v se numeste baza arcului, iar w se numeste varful arcului. Se spune ca nodul w este nod adiacent lui v. Grafic , nodurile unui digraf se pot reprezenta prin cercuri sau patrate, iar arcurile prin sageti. Daca acestea sunt marcate cu numere sau nume , se spune ca sunt etichetate. Orice graf poate fi considerat digraf daca inlocuim o muchie (v,w) cu arcele (v,w) si (w,v).

O notiune importanta in legatura cu digrafurile este notiunea de drum sau cale. Un drum este o succesiune de varfuri v_1, v_2, v_3 .,v_k astfel incat exista arcele (v_1, v_2),

(v_2, v_3),.., (v_k-1, v_k). Daca un arc nu este etichetat , se considera ca este de lungime 1. Valoarea indicata de eticheta unui arc se numeste costul arcului. Un caz particular de drum este ciclul. Ciclul este un drum de la un varf la el insusi. Un digraf fara cicluri se numeste digraf aciclic.

Exista doua reprezentari frecvent utilizate pentru digrafuri :cu ajutorul matricii de adiacenta si cu ajutorul listelor de adiacenta.

Daca G=(V,E) este un digraf iar V= atunci matricea de adiacenta se defineste ca fiind matricea patrata A(nxn), astfel incat A[i,j]=1 daca exista arc de la nodul i la nodul j si A[i,j]=0 daca nu exista arc de la nodul i la nodul j. Avantajul reprezentarii unui digraf prin matrice de adiacenta permite accesul rapid la arcele grafurilor. In acelasi timp, aceasta reprezentare permite demonstrarea eleganta a unor importante teoreme din teoria grafurilor. Pe de alta parte, se poate constata cu usurinta faptul ca, in cazul unor grupuri de obiecte cu legaturi slabe intre ele , matricea de adiacenta este rara si deci mai putin recomandata pentru reprezentare.

O alternativa la reprezentarea prin matricea de adiacenta este lista de adiacenta. Intr-o lista de adiacenta toate nodurile i sunt indici intr-un vector x. In fiecare celula x[i] este memorata adresa unei liste care contine nodurile adiacente nodului x[i]. Implementarea listelor de adiacenta poate fi statica sau dinamica.