10. Grafuri

10.1. Grafuri neorientate

10.1.1. Noţiuni teoretice

Definiţie. Se numeşte graf neorientat o pereche ordonată de mulţimi ( X , U ), X fiind o mulţime finită şi nevidă de elemente, numite vârfuri, iar U o mulţime de perechi neordonate din X, numite muchii.Notăm G = ( X , U ) un graf neneorientat

X se numeşte mulţimea vârfurilorU se numeşte mulţimea muchiilorFie u U care trece prin x, y. Atunci u = [ x , y ] sau u = ( x , y )

Definiţie. Pentru o muchie u = [ x , y ] :– vârfurile x şi y sunt adiacente şi se numesc extremităţile muchiei u; – muchia u şi vârful x sunt incidente în graf; – muchia u şi vârful y sunt incidente în graf; Observaţie. [ x , y ] = [ y , x ] deoarece nu există o orientare a muchieiExemplu. Fie G = ( X , U ) astfel încât :

X = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 }U = { [ 1 , 5 ] , [ 3 , 7 ] , [ 4 , 6 ] , [ 9 , 8 ] , [ 10 , 2 ] , [ 1 , 2 ] , [ 9 , 4 ] , [ 1 , 10] , [ 6 , 8 ] }

Definiţie. Gradul unui varf x, notat d ( x ), reprezintă numărul muchiilor care trec prin vârful x ( incidente cu vârful x ).Definiţie. Un varf care are gradul 0, se numeşte vârf izolat.

Un vârf care are gradul 1, se numeşte vârf terminal.Exemplu. d ( 1 ) = 3; d ( 2 ) = 2; d ( 4 ) = 2; d ( 6 ) = 2; d ( 8 ) = 2; d ( 9 ) = 2; d ( 10 ) = 2;

d ( 11 ) = 0 11 = vârf izolatd ( 3 ) = 1; d ( 5 ) = 1; d ( 7 ) = 1 3 , 5 , 7 = vârfuri terminale

Definiţie. Fie graful G=(X,U). Un graf parţial al lui G, este un graf G1=(X,V) astfel încât V U, adică G 1 are aceeaşi mulţime de vârfuri ca G, iar mulţimea de muchii V este chiar U sau o submulţime a acesteia.Exemplu. G 1 = ( X , V ) V = { [ 1 , 5 ] , [ 2 , 10 ] , [ 6 , 4 ] }

Definiţie. Fie G = ( X , U ). Un subgraf al lui G, este un graf G 1 = ( Y , T ) astfel încât Y X, iar T conţine toate muchiile din U care au ambele extremităţi în Y ( se obţine din G eliminând o parte din vârfuri şi toate muchiile incidente la acestea ).Exemplu. Y = { 1 , 2 , 3 , 7 , 10 } T = { [ 1 , 2 ] , [ 1 , 10 ] , [ 2 , 10 ] , [ 3 , 7 ] }

45

1

32

Definiţie. Se numeşte graf complet cu n vârfuri, notat K n , un graf G = ( X , U ) care are proprietatea că oricare 2 vârfuri diferite sunt adiacente, adică :

x , y X u = [ x , y ] UExemplu. graf complet cu 5 vărfuri K 5

Un graf complet cu n noduri are n*(n-1)/2 muchii.Definiţie. Se numeşte graf bipartit, un graf G = ( X , U ) cu proprietatea că există 2 mulţimi A şi B incluse în X, astfel încât :– A U B = X , A B = – toate muchiile grafului au o extremitate în A şi cealaltă în B. Exemplu. graf bipartit A = { 1 , 2 , 4 } B = { 3 , 5 , 6 , 7 }

Definiţie. Se numeşte graf bipartit complet, un graf bipartit cu proprietatea că pentru orice vârf x din A şi orice vârf y din B, există muchia [ x , y ].Exemplu. graf bipartit complet A = { 1 , 3 , 4 } B = { 2 , 5 }

Definiţie. Se numeşte lanţ în graful G, o succesiune de vârfuri L = ( z 1 , z 2 , … , z k ), unde z 1 , z 2 , … , z k X, astfel încât oricare două vârfuri consecutive sunt adiacente, adică [ z 1 , z 2 ] , [ z 2 , z 3 ] , … , [ z k–1 , z k ] U.

Vârfurile z 1 şi z k se numesc extremităţile lanţului.Numărul de muchii care intră în componenţa sa reprezintă lungimea lanţului.Dacă vârfurile z 1 , z 2 , … , z k sunt distincte două câte două, lanţul se numeşte elementar. În caz contrar, lanţul se numeşte neelementar.

Exemplu:

Lanţ elementar:1,2,3,4,5; 6,7,3,9,4,8…Lanţ neelementar: 1,2,3,2;

1

24

356

7

Definiţie. Se numeşte ciclu într–un graf, un lanţ L = ( z 1 , z 2 , … , z k ) cu proprietatea că z 1 = z k şi muchiile [ z 1 , z 2 ] , [ z 2 , z 3 ] , … , [ z k–1 , z k ] sunt distincte două câte două.Dacă într–un ciclu, toate vârfurile cu excepţia primului şi a ultimului sunt distincte două câte două, atunci ciclul se numeşte elementar. În caz contrar se numeşte neelementar.Exemplu: c1=(3,4,5,3,7,6,1,2,3) ciclu neelementar

c2=(1,2,3,7,6,1) ciclu elementar

Reprezentarea grafurilor neorientate

Fie G = ( X , U ) cu m muchii şi n vârfuri numerotate 1, 2, …, n.1. Reprezentare prin matrice de adiacenţă.

a M n x n a [ i , j ] = {1 , daca ∃[ i , j ] cu i ≠ j ¿ ¿¿¿

Observaţie. Pentru orice graf neneorientat, matricea de adiacenţă a este simetrică faţă de diagonala principală.

2 3

1 4

a=(0 1 0 01 0 1 10 1 0 10 1 1 0

)2. Reprezentare prin liste de adiacenţă

Nodul Lista de adiacenţă

1234

21 , 3 , 42 , 42 , 3

Proprietăţi ale grafurilor neorientate

Teoremă. Într–un graf G = ( X , U ) cu n vârfuri şi m muchii, suma gradelor tuturor vârfurilor este egală cu dublul numărului de muchii.

d ( x 1 ) + d ( x 2 ) + … + d ( x n ) = 2 mConsecinţă. În orice graf există un număr par de vârfuri cu grade impare.Teoremă. Numărul total de grafuri neorientate cu n vârfuri este 2 n * ( n – 1 ) / 2 .Teoremă. Un graf complet cu n vârfuri, are n ( n – 1 ) / 2 muchii.

Conexitate. Descompunerea unui graf în componente conexe

Definiţie. Un graf G este conex, dacă oricare ar fi două vârfuri ale sale, există un lanţ care le leagă.Observaţie. Dacă graful nu este conex, un graf poate fi descompus în componente conexe.Definiţie. Se numeşte componentă conexă a grafului G = ( X , U ), un subgraf G 1 = ( X1, U 1 ) a lui G, conex, cu proprietatea că nu există nici un lanţ care să lege un vârf din X 1 cu un vârf din X – X 1 .

Exemplu.

Grafuri hamiltoniene şi euleriene

Definiţie. Se numeşte ciclu hamiltonian într–un graf, un ciclu elementar care conţine toate vârfurile grafului.

Se numeşte graf hamiltonian, un graf care conţine un ciclu hamiltonian. Un graf complet este hamiltonian.

Se numeşte lanţ hamiltonian într–un graf, un lanţ elementar care conţine toate vârfurile grafului.Teoremă. Dacă într–un graf G = ( X , U ) cu n >= 3 vârfuri, gradul fiecărui vârf x verifică condiţia d ( x ) >= n/2, atunci graful este hamiltonian.Definiţie. Se numeşte ciclu eulerian într–un graf, un ciclu care conţine toate muchiile grafului.

Se numeşte graf eulerian, un graf care conţine un ciclu eulerian.Teoremă. Un graf fără vârfuri izolate este eulerian, dacă şi numai dacă este conex, şi gradele tuturor vârfurilor sunt numere pare.Exemplu. Graf hamiltonian Graf eulerian

1

2 3

4

52

3 4 5

6

78

1