Extras din curs
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.
Preview document
Conținut arhivă zip
- Elemente din Teoria Grafurilor.pdf