- 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 -
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.
|
|
|
|
|
|
|
|
|
|
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.