Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Grafuri - Vocabularul de baza

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
LISTE - Sortare prin interschimbare
Functia standard printf
Operatori
FUNCTII SI STRUCTURA PROGRAMULUI
Bucle incuibate
Structura de tip stiva
Functia standard putchar
Tratarea parametrilor din linia de comanda
Switch
METODE DE ELABORARE A ALGORITMILOR.PROGRAMARE DINAMICA.

TERMENI importanti pentru acest document

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, G1 = (N1, A1, g1) si G2 = (N2, A2, g2) se numesc izomorfe, daca exista o bijectie j : N1 N2 cu proprietatea ca aplicatia y : A1 A2, definita prin y(x1,y1) = (j(x1), j(y1)), (x1,y1)IA1, (j(x1), j(y1)) = (x2,y2) IA2, este o bijectie.

Exemplul 1.3

Grafurile G1 = (N1, A1, g1) si G2 = (N2, A2, g2) 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 : A1 A2.

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)),…,Gk(x) = G Gk-1(x)),

si analog

G (x) = G G (x)),…, G–k(x) = G G–(k-1)(x)),…

Un nod zIGk(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 x1 la nodul xk+1, o secventa L = ( x1, a1, x2, …,xk, ak, xk+1), xiIN, i =1,…,k+1, aiIA, i=1,…,k, cu proprietatea ca fiecare arc ai, este de forma (xi, xi+1) sau (xi+1, xi). Daca ai = (xi, xi+1), atunci ai se numeste arc direct al lantului si daca ai=(xi+1, xi), atunci ai 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 ai din secventa este utilizat o singura data si se numeste elementar daca fiecare nod xi din secventa este utilizat o singura data. Daca xk+1= x1, atunci lantul L se numeste ciclu si se noteaza .

Un lant poate fi reprezentat si ca o secventa de arce L = (a1,…, ak) si in cazul cand G = (N, A) este digraf, ca o secventa de noduri L = (x1,…, xk+1).

Exemplul 1.9

Se considera graful orientat din figura 1.1. Secventa    L = (1, a1, 2, a8, 4, a3, 2, a6, 3, a2, 2, a8, 4) = (a1, a8, a3, a6, a2, a8) este un lant, dar nu este nici lant simplu, nici lant elementar. Secventa L = (1, a1, 2, a3, 4, a4, 2, a2, 3, a6, 2) = (a1, a3, a4, a2, a6) este un lant simplu, dar nu este lant elementar. Secventa L = (1, a1, 2, a6, 3, a7, 5, a9, 4)=(a1, a6, a7, a9) este un lant elementar.

Notiunea de lant se poate defini si intr-un graf neorientat G = (N,A,g) ca o secventa L = (x1, a1, x2, …, xk, ak, xk+1) cu proprietatea ca fiecare muchie ai din secventa este de forma ai = [xi, xi+1] si lantul poate fi reprezentat si sub forma L = (a1, …, ak). Un lant L = (x1, a1, x2, …, xk, ak, xk+1) al grafului orientat G = (N,A,g), in care fiecare arc ai este arc direct, adica este de forma ai = (xi,xi+1), se numeste lant orientat sau drum si se noteaza prin D. Un lant orientat cu xk+1 = x1 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, a1, 2, a3, 4, a8, 2, a2, 3, a6, 2, a3, 4, a8, 2) = (a1, a3, a8, a2, a6, a3, a8) este un drum, dar nici drum simplu nici drum elementar. Secventa D = (1, a1, 2, a3, 4, a8, 2, a2, 3, a7, 5) = (a1, a3, a8, a2, a7) este un drum simplu, dar nu este un drum elementar. Secventa D = (3, a6, 2, a4, 4, a9, 5) = (a6, a4, a9) 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 = (mi 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 mi j = mj i pentru i = 1, …, n si j = 1, …, n.






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 858
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site