Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateC
C sharpCalculatoareCorel drawDot netExcelFox pro
FrontpageHardwareHtmlInternetJavaLinux
MatlabMs dosPascalPhpPower pointRetele calculatoare
SqlTutorialsWebdesignWindowsWordXml

Notiuni de baza in teoria grafurilor

calculatoare

+ Font mai mare | - Font mai mic



DOCUMENTE SIMILARE

Trimite pe Messenger
UTILIZAREA TEHNOLOGIILOR IT IN POLIGRAFIE
APLICATII INFORMATICE IN ECONOMIA MODERNA
Perceptia umana si procesarea de imagini
Serviciul IRC (INTERNET Relay Chat)
VERIFICAREA TIPURILOR
Lucrare de atestat informatica Oceanele Terrei
Comenzile sistemului de operare MS-DOS
Programele de aplicatie MICROSOFT OFFICE
Instrumente software - Mediul Integrat Xilinx ISE
MODELAREA LOGICA


Notiuni de baza in teoria grafurilor

Definitie:




Se numeste graf orientat un triplet G = (N, A, g) format dintr-o :

-> multime N de elemente numite noduri sau varfuri

-> familie A de elemente numite arce

-> aplicatie g: A→ N × N numita functie de incidenta, prin care fiecarui element aA i se asociaza o pereche ordonata (x, y) N× N cu xy ; daca eliminam conditia xy 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= 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 xN se reprezinta printr-un punct sau cerculet in plan ;

-> fiecare arc aA, 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.

Exemplu: Graful din figura de mai jos este de ordinul 8.

Figura 1.1.:

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

Exemplu : Cele trei grafuri din figura 1.2. reprezinta acelasi graf .

Figura 1.2.:

Definitie: Doua grafuri orientate, = ( ,, ) si = (, , ) se numesc izomorfe, daca exista o bijectie Φ : cu proprietatea ca aplicatia ψ : , definita prin ψ( x , y ) = (Φ(x ), Φ(y )) , (x , y ) A , (Φ(x ), Φ(y )) A , este o bijectie.

Exemplu: Grafurile G = ( N , A , g ) si G = ( N , A , g prezentate in figura de mai jos sunt izomorfe.

Figura 1.3.:

Daca definim bijectia Φ prin Φ(1) = 4, Φ(3) = 5, Φ(4) = 6, Φ(5) = 1, Φ(6) = 2, atunci ψ(1, 2) = (Φ(1),Φ(2)) = (4, 3) , ψ(1, 4) = (Φ(1),Φ(4)) = (4, 6) , ψ(1, 6) = (Φ(1),Φ(6)) = (4, 2) etc. este evident bijectia ψ : A → A

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

Exemplu: 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 de noteaza G = ( N, A).

Definitie: 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 a A i se asociaza o pereche P (N); daca consideram g : A → P (N) , unde P (N) = P (N) U P (N) , atunci aplicatia g asociaza fiecarui element a A, fie o pereche de noduri P (N) care se noteaza [x, y] sau [y, x], fie un nod 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.

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

Exemplu: 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 neorientat 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).

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

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

Definitie: Fie un arc a = (x, y) A. Nodul x se numeste predecesor al nodului y si nodul y se numeste successor 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) U V (x) se numeste vecinatatea nodului x. Daca V(x) = Ø , atunci x se numeste nod izolat.

Exemplu: In graful din figura 1.1., pentru nodul 4 avem : V (4) = , V (4) = , V(4) = .

Definitie: Se spune ca nodul x este adiacent cu submultimea N Ì N, daca xÏ N si x V(N ), V(N U

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

Definitie: Fie arcul a = ( x, y) 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) U E (x).

Numarul (x) = | E (x) | se numeste semigradul exterior al nodului x, numarul (x) = | E (x) se numeste semigradul interior al nodului x si numarul (x) = (x) + (x) se numeste gradul nodului x.

Exemplu: Se considera multigraful orientat din figura 1.1. Avem

(3) = 1, deci

Daca G = ( N, A, g) este un graf neorintat atunci (x) = . In cazul in care G = ( N, A, g) este multigraf orientat atunci

| V (x) | , ≥ | V (x) | si in care G = ( N, A) este un digraf relatiile sunt verificate cu egalitati. Evident ca daca x este un nod izolat atunci

(x) = 0. Un nod x cu (x) = 1 se numeste perdant. Daca toate nodurile lui G au acelasi grad atunci G se numeste graf – regulat . Un graf 0 – regulat se numeste graf nul si un graf 3 – regulat se numeste graf trivalent sau cubic.

Definitie: Intr-un graf orientat G = ( N, A, g) se numeste lant de la nodul x1 la nodul xk+1, o secventa L = (x , a , x , …., xk, ak, xk+1) , xi N, i = 1,…., k+1, ai A , 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 = x atunci lantul simplu L se numeste ciclu si se noteaza L

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



Exemplu: 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 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 , …., 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 = (a ,…., ak). Un lant L = (x , a , x , …., 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 simplu orientat cu xk+1 = x se numeste ciclu orientat sau circuit si se noteaza prin D Notiunile de drum si circuit au sens numai pentru grafuri orientate.

Exemplu: 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”, ci numai in cazurile cand este necesar.

Definitie: 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 N 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 n n , unde

Evident ca au loc relatiile :

, iN, , , jN .

Matricea de incidenta asociata digrafului G este matricea = (i j n m unde

In acest caz au loc relatiile:






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1859
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