Grafuri. Concepte de baza

Grafuri neorientate

Graful neorientat este o structura G=(N, R), in care N este o multime de noduri , iar R este o multime de muchii . Fiecare muchie este o pereche de noduri (Ni, Nj). Muchia poate fi parcursa in ambele sensuri: de la nodul Ni la nodul Nj sau invers. In reprezentarea grafica, nodurile grafului neorientat sunt reprezentate de obicei prin cercuri, iar muchiile prin segmente de dreapta sau arce de curba. Un exemplu de graf este dat in figura 1.


- Figura 1 -

Se numesc noduri adiacente doua noduri legate direct printr-o muchie. De exemplu, in figura 1 nodurile 3 si 6 sunt adiacente.

Se numeste lant o succesiune de noduri adiacente, in care nici un nod nu se repeta. Exemple de lanturi in figura 1 sunt 4-1-2-3-5-6-7 sau 4-3-2-1.

Se numeste circuit un lant inchis. Exemple de circuite in figura 1 sunt 1-2-3-4-1,  1-2-3-1, 1-3-4-1 si 3-6-5-3. Circuitul nu se autointersecteaza, deoarece nici un nod nu poate apare de doua ori.

Un graf G'=(N', R') este subgraf al lui G, daca multimea N' este inclusa in N, iar multimea R' este inclusa in R.

Graful este conex, daca exista cel putin un lant care uneste oricare doua noduri ale sale. Graful din figura 1 este conex. Un exemplu de graf neconex este dat in figura 2. Se observa ca un graf neconex se imparte in mai multe subgrafuri conexe. In figura 2, subgrafurile conexe sunt cele formate din nodurile [1, 2, 3, 4] si respectiv [5, 6, 7].


- Figura 2 -

Un graf conex care nu contine circuite se numeste arbore liber, deoarece el este un arbore fara radacina. Un astfel de arbore liber este reprezentat in figura 3.


- Figura 3 -

Alegand unul din nodurile arborelui liber drept radacina si aranjand pe niveluri celelalte noduri, se obtine un arbore obisnuit. Astfel s-a procedat in figurile 4.a si 4.b, alegand drept radacina in arborele din figura 3 nodurile 2 si, respectiv, 6.


- Figura 4 -

In cazul grafurilor abstracte, nici nodurile nici muchiile nu contin alte informatii. De cele mai multe ori insa, in practica, nodurile si/sau muchiile grafului poarta anumite informatii suplimentare. Astfel, in cazul grafurilor etichetate, fiecare nod si/sau muchie poarta un simbol numit eticheta. Este posibil, insa, ca nodurilor si/sau muchiilor grafului sa li se ataseze si alte informatii. In cazul grafurilor ponderate, fiecarei muchii i se ataseaza un numar intreg sau real numit pondere. Un exemplu este graful ponderat din figura 5. Acesta ar putea indica, de exemplu, schema drumurilor dintre localitati, in care caz informatiile din noduri sunt denumirile localitatilor, iar ponderile reprezinta lungimile drumurilor respective. Se considera ca fiecare drum poate fi parcurs in ambele sensuri.


- Figura 5 -

Grafuri orientate

Graful orientat, numit si digraf (de la directed graph) este o structura G=(V, E), in care V este o multime de varfuri (engleza: vertex), iar E este o multime de arce (engleza: edge). Arcul este o pereche ordonata de varfuri (Vi, Vj), in care Vi este baza arcului, iar Vj este varful arcului. Doua varfuri ale grafului sunt adiacente daca sunt unite printr-un arc (in cazul nostru, Vi este adiacent lui Vj).

Graful orientat poate fi reprezentat grafic in mod asemanator grafului neorientat, cu deosebirea ca arcele au sageata la varf. Un exemplu de graf orientat este dat in figura 6.


- Figura 6 -

Daca intre doua varfuri exista legaturi directe in ambele sensuri, fiecare din acestea se va reprezenta printr-un arc. Este posibil, de asemenea, sa existe arce, numite bucle, la care atat baza, cat si varful sunt pe acelasi nod, cum sunt cele din nodurile 1 si 4.

Se numeste cale (engleza: path) o succesiune de varfuri adiacente, in care nici un varf nu se repeta. In figura 6 exemple de cai sunt:  1-4-2, 1-2-4-3 sau 1-4-3-2.

Se numeste ciclu o cale inchisa (la care primul si ultimul nod coincid). Exemple de cicluri in figura 6 sunt 1-2-4-1 si 4-3-2-4.

In tabelul de mai jos este sintetizata corespondenta dintre termenii folositi in cazul grafurilor neorientate si al celor orientate.
 
Graf neorientat
Graf orientat
Nod
Varf
Muchie
Arc
Lant
Cale
Circuit
Ciclu

Un graf orientat (digraf) este tare conex daca, oricare ar fi varfurile Vi si Vj, exista o cale de la Vi la Vj si una de la Vj la Vi. Graful din figura 6 este tare conex. Un digraf care nu este tare conex, poate avea subgrafuri tare conexe.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati