Elemente din Teoria Grafurilor

Prima referire la teoria grafurilor a fost facuta în 1736 de catre Euler în lucrarea numita:

Problema podurilor din Königsberg. În 1847 Kirchoff a abordat teoria reCelelor electrice prin

metoda grafurilor.

În 1956 Ford si Fulkerson au aplicat teoria grafurilor în reCelele de transport. Astfel, dupa

aceasta perioada teoria grafurilor a fost utilizata pentru rezolvarea unor probleme cu caracter

economic, pentru proiectarea reCelelor electrice, de canalizare, de gaze sau a reCelelor de tehnica

de calcul, ori în medicina.

DefiniCie.. Un graf G este o pereche de forma G = (X ,“) unde: X este este o mulCime

finita numita mulCimea vârfurilor (sau a nodurilor); orice element x X se numeste vârf, “

este o submulCime a lui X × X , mulCimea perechilor ordonate ( ) i j x , x , , i j x x  X , i =1,n ,

j =1, n , i ` j numite arce.

Pentru un arc ( )“ i j x , x vârful i x se numeste extremitate iniCiala (sursa), iar vârful j x

extremitate finala (destinaCie).

Graful G admite o reprezentare geometrica în plan, obCinuta astfel:

- vârfurile se plaseaza în plan în poziCii distincte oarecare.

- fiecare arc ( )“ i j x , x se reprezinta printr-o linie ce uneste cele 2 extremitaCi si pe care se afla

sensul de la i x la j x .

Exemplu: Fie graful G = (X ,“) dat de { } 1 2 3 4 5 X = x , x , x , x , x iar

{( ) ( ) ( ) ( ) ( ) ( ) ( )} 1 2 1 3 2 4 3 2 3 4 4 1 4 5 “ = x , x , x , x , x , x , x , x , x , x , x , x , x , x .

Cu reprezentarea geometrica:

Figura 5.1.1.

Se observa ca “ poate fi definita ca o aplicaCie multivoca “ : X ’ P( X ) adica, “(x) este

mulCimea tuturor nodurilor finale ale arcelor ce au ca nod iniCial pe x .

Astfel, graful din exemplul de mai sus poate fi scris ca { } 1 2 3 4 5 X = x , x , x , x , x ,

( ) { } 1 2 3 “ x = x , x , ( ) { } 2 4 “ x = x , ( ) { } 3 2 4 “ x = x , x , ( ) { } 4 1 5 “ x = x , x , “( ) =  5 x

Daca ( ) i i x “ x , arcul ( )“ i i x , x se numeste bucla.

Daca graful G conCine arcul ( ) i j x , x vom spune ca vârfurile i x si j x sunt adiacente în G

si amândoua sunt incidente cu arcul ( ) i j x , x .

DefiniCie. O succesiune de arce în care vârful terminal al unuia este origine pentru

urmatorul se numeste drum.

DefiniCie. Un drum este simplu daca foloseste un arc o singura data.

DefiniCie.. Un drum este elementar daca nu trece de doua ori prin acelasi vârf.

DefiniCie. Un drum elementar care cuprinde toate vârfurile grafului se numeste

hamiltonian.

DefiniCie. Numarul arcelor care compun un drum se numeste lungimea acelui drum.

Pentru exemplul grafului din figura 5.1.1, un drum elementar poate fi 1 { 1 2 4 5} d : x , x , x , x ,

lungimea drumului 1 d este 3.

Într-un graf G , se numeste muchie o pereche de vârfuri [ ] i j x , x de vârfuri pentru care

avem proprietatea ca ( )“ i j x , x sau ( )“ j i x , x ; muchiile unui graf reprezentat geometric se

prezinta ca niste segmente neorientate.

DefiniCie. Se numeste lanC un sir de arce {( ) ( ) ( )} 1 2 3 4 1 , , , ,..., , + = p p l x x x x x x cu

proprietatea ca oricare arce vecine ( ) 1 , i i+ x x , ( ) 2 3 , i+ i+ x x au o extremitate comuna pentru orice

i = 1,2,...p  2 .

DefiniCie. Un lanC care nu-si repeta vârfurile se numeste lanC elementar, iar un lanC care

nu-si repeta muchiile se numeste un lanC simplu.

Numarul de muchii care formeaza un lanC se numeste lungimea lanCului.

Exemplu

În graful din figura 5.1.2. urmatoarele siruri de arce sunt lanCuri:

{( ) ( ) ( )} 1 1 2 2 4 4 3 l : x , x , x x , x , x , {( ) ( )} 2 1 2 2 4 l : x , x , x , x , {( ) ( ) ( )} 3 1 3 3 2 2 4 l : x , x , x , x , x , x ,

{( ) ( ) ( )} 4 1 4 4 3 3 2 l : x , x , x , x , x , x

DefiniCie. Se spune ca un graf este conex daca între oricare doua vârfuri ale sale exista cel

puCin un lanC care sa le lege. În caz contrar graful este neconex.

Un graf se numeste tare conex daca între oricare doua vârfuri ale sale exista cel puCin un

drum.