Grafuri. Concepte de bază

Grafuri neorientate

Graful neorientat este o structură G=(N, R), în care N este o mulțime de noduri , iar R este o mulțime de muchii . Fiecare muchie este o pereche de noduri (Ni,Nj). Muchia poate fi parcursă în ambele sensuri: de la nodul Ni la nodul Nj sau invers. În reprezentarea grafică, nodurile grafului neorientat sunt reprezentate de obicei prin cercuri, iar muchiile prin segmente de dreaptă sau arce de curbă. Un exemplu de graf este dat în figura 1.


- Figura 1 -

Se numesc noduri adiacente două noduri legate direct printr-o muchie. De exemplu, în figura 1 nodurile 3 si 6 sunt adiacente.

Se numește lanț o succesiune de noduri adiacente, în care nici un nod nu se repetă. Exemple de lanțuri în figura 1 sunt 4-1-2-3-5-6-7 sau 4-3-2-1.

Se numește circuit un lanț închis. Exemple de circuite în figura 1 sunt 1-2-3-4-1,  1-2-3-1, 1-3-4-1 si 3-6-5-3. Circuitul nu se autointersectează, deoarece nici un nod nu poate apare de două ori (cu excepția primului, care apare și ca nod ultim).

Un graf G'=(N', R') este subgraf al lui G, dacă mulțimea N' este inclusă în N, iar mulțimea R' este inclusă în R.

Graful este conex, dacă oricare două noduri ale sale sunt legate între ele prin cel puțin un lanț. Graful din figura 1 este conex. Un exemplu de graf neconex este dat în figura 2. Se observă că un graf neconex se împarte în mai multe subgrafuri conexe. În figura 2, subgrafurile conexe sunt cele formate din nodurile [1, 2, 3, 4] și respectiv [5, 6, 7].


- Figura 2 -

Un graf conex care nu conține circuite se numește arbore liber, deoarece el este un arbore fară rădăcină. Un astfel de arbore liber este reprezentat în figura 3.


- Figura 3 -

Alegând unul din nodurile arborelui liber drept rădăcină și aranjând pe niveluri celelalte noduri, se obține un arbore obișnuit. Astfel s-a procedat în figurile 4.a si 4.b, alegând drept rădăcină în arborele din figura 3 nodurile 2 și, respectiv, 6.


- Figura 4 -

În cazul grafurilor abstracte, nici nodurile și nici muchiile nu conțin alte informații. De cele mai multe ori însă, în practică, nodurile și/sau muchiile grafului poartă anumite informații suplimentare. Astfel, în cazul grafurilor etichetate, fiecare nod și/sau muchie poartă un simbol numit etichetă. Este posibil, însă, ca nodurilor și/sau muchiilor grafului să li se atașeze și alte informații. În cazul grafurilor ponderate, fiecărei muchii i se atașează un număr întreg sau real numit pondere. Un exemplu este graful ponderat din figura 5. Acesta ar putea indica, de exemplu, schema drumurilor dintre localități, în care caz informațiile din noduri sunt denumirile localităților, iar ponderile reprezintă lungimile drumurilor respective. Se consideră că fiecare drum poate fi parcurs în ambele sensuri.


- Figura 5 -

Grafuri orientate

Graful orientat, numit și digraf (de la directed graph) este o structură G=(V, E), în care V este o mulțime de vârfuri (engleză: vertex), iar E este o mulțime de arce (engleză: edge). Arcul este o pereche ordonată de vârfuri (Vi, Vj), în care Vi este baza arcului, iar Vj este vârful arcului. Două vârfuri ale grafului sunt adiacente dacă sunt unite printr-un arc (în cazul nostru, Vi este adiacent lui Vj).

Graful orientat poate fi reprezentat grafic în mod asemănător grafului neorientat, cu deosebirea că arcele au săgeata la vârf. Un exemplu de graf orientat este dat în figura 6.


- Figura 6 -

Dacă între două vârfuri există legături directe în ambele sensuri, fiecare din acestea se va reprezenta printr-un arc. Este posibil, de asemenea, să existe arce, numite bucle, la care atât baza, cât și vârful sunt pe același nod, cum sunt cele din nodurile 1 si 4.

Se numește cale (engleză: path) o succesiune de vârfuri adiacente, în care nici un vârf nu se repetă. În figura 6 exemple de căi sunt:  1-4-2, 1-2-4-3 sau 1-4-3-2.

Se numește ciclu o cale închisă (la care primul și ultimul nod coincid). Exemple de cicluri în figura 6 sunt 1-2-4-1 si 4-3-2-4.

În tabelul de mai jos este sintetizată corespondența dintre termenii folosiți în cazul grafurilor neorientate și al celor orientate.
 
Graf neorientat
Graf orientat
Nod
Vârf
Muchie
Arc
Lanț
Cale
Circuit
Ciclu

Un graf orientat (digraf) este tare conex dacă, oricare ar fi vârfurile Vi si Vj, există o cale de la Vi la Vj și 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 (numite și "componente tare conexe" ale grafului).



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați