Elemente din teoria grafurilor. - Bazele Cercetarii Operationale

Extras din document

Prima referire la teoria grafurilor a fost facuta in 1736 de catre Euler. In 1847 Kirchoff a abordat teoria retelelor electrice prin teoria grafurilor. In 1956 Ford si Fulkerson au aplicat teoria grafurilor in retelele de transport. Astfel, dupa aceasta perioada teoria grafurilor a fost utilizata pentru rezolvarea unor probleme cu caracter economic, pentru proiectarea retelelor electrice, de canalizare, de gaze sau a retelelor de tehnica de calcul. Def-Un graf G este o pereche de forma G =(X,Г)unde: X este este o multime finită numită multimea nodurilor; orice element x se numeste varf, Г este o submultime a lui X *X , multimea perechilor ordonate (xi,xj), xi,xj din X , i =1,n j =1, n si i <> j numite arce. Pentru un arc  (xi,xj) din Г varful xi se numeste sursă, iar varful xj destinatie. Graful G admite o reprezentare geometrică in plan, obtinută astfel: - varfurile se plasează in plan in pozitii distincte oarecare. - fiecare arc  (xi,xj) din Г se reprezintă printr-o linie ce uneste sursa -destinatie Def. O succesiune de arce in care varful terminal al unuia este origine pentru următorul se numeste drum. Def. Un drum este simplu dacă foloseste un arc o singură dată. Un drum este elementar dacă nu trece de două ori prin acelasi varf. Def. Numărul arcelor care compun un drum se numeste lungimea acelui drum. Intr-un graf G , se numeste muchie o pereche de varfuri (xi,xj) Se numeste lant un sir de arce cu proprietatea că oricare arce vecine x i, x i1, x i2,x i2au o extremitate comună pentru orice i =1,2,...p-2 . ...