Grafuri - Vocabularul de baza

Grafuri - Vocabularul de baza

Avertizam cititorul ca terminologia din Teoria Grafurilor nu este complet unitara. Vom pastra, in cea mai mare parte, terminologia consacrata in literatura romana de specialitate.

Definitia 1.1

Se numeste graf orientat un triplet G = (N, A, g), format dintr-o multime N de elemente numite noduri sau varfuri, dintr-o familie A de elemente numite arce si dintr-o aplicatie g : A NxN numita functie de incidenta, prin care fiecarui element aIA i se asociaza o pereche ordonata (x, y) I NxN cu x y; daca eliminam conditia x y, atunci arcul de forma (x,x) se numeste bucla, iar G se numeste graf general orientat.

In continuare, vom presupune ca graful orientat G este finit, adica multimea nodurilor N = este finita si familia arcelor A = (., a,.) este un sir finit. Cardinalul multimii N, notat |N| = n, se numeste ordinul grafului orientat G.

Un graf orientat G = (N, A, g) se reprezinta grafic in modul urmator:

fiecare nod xIN se reprezinta printr-un punct sau cerculet in plan;

fiecare arc aIA, a=(x,y) se reprezinta printr-o linie care uneste cele doua noduri si pe care se afla o sageata cu sensul de la x la y.

Exemplul 1.1

Graful din figura 1.1 este de ordinul 8.

Observatia 1.1

Reprezentarea grafica a unui graf orientat G = (N, A, g) nu este unica. In primul rand, nodurile se pot plasa in plan la intamplare. In al doilea rand, nu este obligatoriu ca arcele sa fie segmente de dreapta.

Exemplul 1.2

Cele trei grafuri din figura 1.2 reprezinta acelasi graf.

Definitia 1.2

Doua grafuri orientate, G₁ = (N₁, A₁, g₁) si G₂ = (N_2, A₂, g₂) se numesc izomorfe, daca exista o bijectie j : N₁ N₂ cu proprietatea ca aplicatia y : A₁ A₂, definita prin y(x₁,y₁) = (j(x₁), j(y₁)), (x₁,y₁)IA₁, (j(x₁), j(y₁)) = (x₂,y₂) IA₂, este o bijectie.

Exemplul 1.3

Grafurile G₁ = (N₁, A₁, g₁) si G₂ = (N_2, A₂, g₂) prezentate in figura 1.3 sunt izomorfe.

Daca definim bijectia j prin j j j j j j(6)=2, atunci y j j y j j y j j(6)) = (4,2), etc. este evident bijectia y : A₁ A₂.

Definitia 1.3

Daca oricare pereche ordonata (x,y) I NxN este imaginea a cel mult q, q>1, elemente din A, atunci G = (N, A, g) se numeste multigraf orientat.

Exemplul 1.4

In figura 1.1 avem un multigraf orientat cu q=2.

In paragrafele si capitolele urmatoare ne vom ocupa de grafuri orientate cu q=1. In acest caz, functia g este injectiva si familia A este o multime. Un astfel de graf se numeste digraf si se noteaza G = (N, A).

Definitia 1.4

Se numeste graf neorientat un triplet G = (N, A, g) format dintr-o multime N de elemente numite noduri sau varfuri, dintr-o familie A de elemente numite muchii si dintr-o aplicatie g : A P (N) numita functie de incidenta, prin care fiecarui element aIA i se asociaza o pereche I P (N); daca consideram g : A P (N) unde P (N) = P (N) P (N) atunci aplicatia g asociaza fiecarui element aIA, fie o pereche de noduri I P (N) care se noteaza [x,y] sau [y,x], fie un nod I P (N) care se noteaza [x,x] si se numeste bucla, iar G se numeste graf general neorientat.

In continuare, vom presupune ca graful neorientat G este finit, adica multimea nodurilor N este finita si familia muchiilor A este un sir finit.

Un graf neorientat G = (N, A, g) se reprezinta grafic la fel ca in cazul grafurilor orientate cu deosebirea ca o muchie a=[x,y] se reprezinta printr-o linie care uneste cele doua noduri fara sageata care precizeaza sensul in cazul arcului. De asemenea, la fel ca in cazul grafurilor orientate se defineste izomorfismul a doua grafuri neorientate.

Definitia 1.5

Daca oricare pereche [x,y] I P (N) este imaginea a cel mult q, q>1, elemente din A, atunci G = (N, A, g) se numeste multigraf neorientat.

Exemplul 1.5

Daca se elimina sageata de pe fiecare arc al grafului din figura 1.1, atunci fiecare arc (x,y) devine o muchie [x,y] si graful devine un multigraf cu q=3.

In paragrafele si capitolele urmatoare ne vom ocupa de grafuri neorientate cu q=1. In acest caz, functia g este injectiva si familia A este o multime. Un graf neorientat cu q=1 se numeste graf simplu si se noteaza G = (N, A).

In majoritatea problemelor prezentate in continuare, se presupune ca graful este orientat. De aceea vom prezenta definitiile pentru grafurile orientate. Definitiile pentru grafurile neorientate se pot deduce in cele mai multe cazuri, cu usurinta, din definitiile corespunzatoare pentru grafuri orientate. Totusi, vom face unele precizari referitor la unele definitii pentru grafurile neorientate.

Definitia 1.6

Fie un arc a = (x,y) I A. Nodurile x, y se numesc extremitatile arcului, nodul x este extremitatea initiala si y extremitatea finala; nodurile x, y se numesc adiacente.

Evident ca, pentru o muchie a = [x,y] I A, nu se pot preciza extremitatea initiala si extremitatea finala.

Definitia 1.7

Fie un arc a = (x,y) I A. Nodul x se numeste predecesor al nodului y si nodul y se numeste succesor al nodului x. Multimea succesorilor nodului x este multimea V⁺(x) = si multimea predecesorilor nodului x este multimea V^-(x) = . Multimea V(x) = V⁺(x) V^-(x) se numeste vecinatatea nodului x. Daca V(x)= , atunci x se numeste nod izolat.

Exemplul 1.6

Pentru 2-graful din figura 1.1. avem V⁺(4)=, V^-(4)=, V(4)=.

Definitia 1.8

Se spune ca nodul x este adiacent cu submultimea N N, daca x N si xIV(N ), V(N

Observatia 1.2

Conceptul de digraf se poate defini si prin perechea G = (N, G), unde N = este multimea nodurilor si G este aplicatia multivoca G : N P (N), G(x) = V⁺(x), xIN. Cele doua definitii sunt echivalente. Intr-adevar, daca digraful este dat sub forma G = (N, A), atunci G(x) = V⁺(x), xIN. Reciproc, daca digraful este dat sub forma G = (N, G G(x) = V⁺(x), xIN, atunci se determina E⁺(x) = , xIN si A = . De asemenea, se defineste G (x) = V^-(x), xIN. Recursiv avem:

G (x) = G G(x)),.,G^k(x) = G G^k-1(x)),

si analog

G (x) = G G (x)),., G^-k(x) = G G^-(k-1)(x)),.

Un nod zIG^k(x) se numeste descendent al nodului x si un nod uIG^-k(x) se numeste ascendent al nodului x.

Exemplul 1.7

Fie digraful din figura 1.4

Daca digraful este dat sub forma G = (N, A) cu N = , A = = , atunci G(1) = V⁺(1) = , G(1) = V⁺(1) = , G(2) = V⁺(2) = , G(3) = V⁺(3) = si am obtinut digraful sub forma G = (N, G

Daca digraful este dat sub forma G = (N, G) cu N = , G G G , atunci E⁺(1) = , E⁺(2) = , E⁺(3) = si A = E⁺(1) E⁺(2) E⁺(3) = = .

Definitia 1.9

Doua arce se numesc adiacente daca au cel putin o extremitate in comun.

Definitia 1.10

Fie arcul a = (x,y) I A. Se spune ca arcul a este incident catre exterior la nodul x si incident catre interior la nodul y. Multimea arcelor incidente catre exterior la nodul x este E⁺(x) = , multimea arcelor incidente catre interior la nodul x este E^-(x) = si multimea arcelor incidente la nodul x este E(x) = E⁺(x) E^-(x). Numarul r (x) = |E⁺(x)| se numeste semigradul exterior al nodului x, numarul r (x) = |E^-(x)| se numeste semigradul interior al nodului x si numarul r(x) = r (x) + r (x) se numeste gradul nodului x.

Exemplul 1.8

Se considera multigraful orientat din figura 1.1. Avem r r (3)=1, deci r

Daca G = (N, A, g) este un graf neorientat, atunci r(x) = r (x) =    r (x). In cazul in care G = (N, A, g) este multigraf orientat, atunci r (x) |V⁺(x)|, r (x) |V^-(x)| si in cazul in care G = (N, A) este un digraf, relatiile sunt verificate cu egalitati. Evident ca daca x este nod izolat, atunci r(x) = 0. Un nod x cu r(x) = 1 se numeste pendant. Daca toate nodurile lui G au acelasi grad r, atunci G se numeste graf r-regulat. Un graf 0-regulat se numeste graf nul si un graf 3-regulat se numeste graf trivalent sau cubic.

Definitia 1.11

Intr-un graf orientat G = (N, A, g), se numeste lant de la nodul x₁ la nodul x_k+1, o secventa L = ( x₁, a₁, x₂, .,x_k, a_k, x_k+1), x_iIN, i =1,.,k+1, a_iIA, i=1,.,k, cu proprietatea ca fiecare arc a_i, este de forma (x_i, x_i+1) sau (x_i+1, x_i). Daca a_i = (x_i, x_i+1), atunci a_i se numeste arc direct al lantului si daca a_i=(x_i+1, x_i), atunci a_i se numeste arc invers al lantului. Numarul de arce din secventa este, prin definitie, lungimea lantului L. Lantul L se numeste simplu, daca fiecare arc a_i din secventa este utilizat o singura data si se numeste elementar daca fiecare nod x_i din secventa este utilizat o singura data. Daca x_k+1= x₁, atunci lantul L se numeste ciclu si se noteaza .

Un lant poate fi reprezentat si ca o secventa de arce L = (a₁,., a_k) si in cazul cand G = (N, A) este digraf, ca o secventa de noduri L = (x₁,., x_k+1).

Exemplul 1.9

Se considera graful orientat din figura 1.1. Secventa    L = (1, a₁, 2, a₈, 4, a₃, 2, a₆, 3, a₂, 2, a₈, 4) = (a₁, a₈, a₃, a₆, a₂, a₈) este un lant, dar nu este nici lant simplu, nici lant elementar. Secventa L = (1, a₁, 2, a₃, 4, a₄, 2, a₂, 3, a₆, 2) = (a₁, a₃, a₄, a₂, a₆) este un lant simplu, dar nu este lant elementar. Secventa L = (1, a₁, 2, a₆, 3, a₇, 5, a₉, 4)=(a₁, a₆, a₇, a₉) este un lant elementar.

Notiunea de lant se poate defini si intr-un graf neorientat G = (N,A,g) ca o secventa L = (x₁, a₁, x₂, ., x_k, a_k, x_k+1) cu proprietatea ca fiecare muchie a_i din secventa este de forma a_i = [x_i, x_i+1] si lantul poate fi reprezentat si sub forma L = (a₁, ., a_k). Un lant L = (x₁, a₁, x₂, ., x_k, a_k, x_k+1) al grafului orientat G = (N,A,g), in care fiecare arc a_i este arc direct, adica este de forma a_i = (x_i,x_i+1), se numeste lant orientat sau drum si se noteaza prin D. Un lant orientat cu x_k+1 = x₁ se numeste ciclu orientat sau circuit si se noteaza prin . Notiunile de drum si circuit au sens numai pentru grafuri orientate.

Exemplul 1.10

Se considera graful orientat din figura 1.1. Secventa D = (1, a₁, 2, a₃, 4, a₈, 2, a₂, 3, a₆, 2, a₃, 4, a₈, 2) = (a₁, a₃, a₈, a₂, a₆, a₃, a₈) este un drum, dar nici drum simplu nici drum elementar. Secventa D = (1, a₁, 2, a₃, 4, a₈, 2, a₂, 3, a₇, 5) = (a₁, a₃, a₈, a₂, a₇) este un drum simplu, dar nu este un drum elementar. Secventa D = (3, a₆, 2, a₄, 4, a₉, 5) = (a₆, a₄, a₉) este un drum elementar.

In paragrafele urmatoare vom considera, in general, lanturi si drumuri elementare, dar fara a mai specifica de fiecare data atributul "elementar", decat numai in cazurile cand este necesar.

Definitia 1.12

Se spune ca graful orientat G = (N , A , g ) este un subgraf al grafului orientat G = (N, A, g) daca N N si A A . Daca N N si A = (N xN A atunci G = (N , A , g ) se numeste subgraf indus in G de multimea de noduri N . Daca N = N si A A atunci G = (N , A , g ) se numeste subgraf partial al lui G.

Concepte similare se pot defini in mod analog si pentru grafuri neorientate.

Fie G = (N, A) un digraf cu multimea nodurilor N = si multimea arcelor A = . Matricea de adiacenta asociata digrafului G este matricea M = (m_{i j})_nxn unde

Evident, au loc relatiile: si .

Matricea de incidenta asociata digrafului G este matricea

unde

In acest caz au loc relatiile: , .

Exemplul 1.11

Pentru digraful din figura 1.4. avem

Se remarca faptul ca matricea de incidenta are pe fiecare coloana un 1, un -1 si n-2 zerouri.

Daca G = (N, A) este un graf simplu neorientat atunci

si

Evident ca in cazul unui graf simplu neorientat, matricea de adiacenta M este simetrica, adica m_{i j} = m_{j i} pentru i = 1, ., n si j = 1, ., n.