Matematici Aplicate în Economie

ELEMENTE DE TEORIA GRAFURILOR

1. Introducere. Definitii

Prima referire la teoria grafurilor a fost făcută în 1736 de către Euler în lucrarea numită:

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

metoda grafurilor.

În 1956 Ford si Fulkerson au aplicat teoria grafurilor în retelele de transport. Astfel, după

această perioadă teoria grafurilor a fost utilizată pentru rezolvarea unor probleme cu caracter

economic, pentru proiectarea retelelor electrice, de canalizare, de gaze sau a retelelor de tehnică

de calcul, ori în medicină.

Definitie.. Un graf G este o pereche de forma G = (X ,G) unde: X este este o multime

finită numită multimea vârfurilor (sau a nodurilor); orice element xÎ X se numeste vârf, G

este o submultime a lui X ´ X , multimea perechilor ordonate ( ) i j x , x , , i j x x Î X , i =1,n ,

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

Pentru un arc ( )ÎG i j x , x vârful i x se numeste extremitate initială (sursă), iar vârful j x

extremitate finală (destinatie).

Graful G admite o reprezentare geometrică în plan, obtinută astfel:

- vârfurile se plasează în plan în pozitii distincte oarecare.

- fiecare arc ( )ÎG i j x , x se reprezintă printr-o linie ce uneste cele 2 extremităti si pe care se află

sensul de la i x la j x .

Exemplu: Fie graful G = (X ,G) 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 G = x , x , x , x , x , x , x , x , x , x , x , x , x , x .

Cu reprezentarea geometrică:

Figura 5.1.1.

Se observă că G poate fi definită ca o aplicatie multivocă G : X ® P( X ) adică, G(x) este

multimea tuturor nodurilor finale ale arcelor ce au ca nod initial 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 G x = x , x , ( ) { } 2 4 G x = x , ( ) { } 3 2 4 G x = x , x , ( ) { } 4 1 5 G x = x , x , G( ) = Æ 5 x

Dacă ( ) i i x ÎG x , arcul ( )ÎG i i x , x se numeste buclă.

Dacă graful G contine arcul ( i j ) x , x vom spune că vârfurile i x si j x sunt adiacente în G

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

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

următorul se numeste drum.

Definitie. Un drum este simplu dacă foloseste un arc o singură dată.

Definitie.. Un drum este elementar dacă nu trece de două ori prin acelasi vârf.

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

hamiltonian.

Definitie. Numărul 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 că ( )ÎG i j x , x sau ( )ÎG j i x , x ; muchiile unui graf reprezentat geometric se

prezintă ca niste segmente neorientate.

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

proprietatea că oricare arce vecine ( ) 1 , i i+ x x , ( ) 2 3 , i+ i+ x x au o extremitate comună pentru orice

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

Definitie. Un lant care nu-si repetă vârfurile se numeste lant elementar, iar un lant care

nu-si repetă muchiile se numeste un lant simplu.

Numărul de muchii care formează un lant se numeste lungimea lantului.

Exemplu

În graful din figura 5.1.2. următoarele siruri de arce sunt lanturi:

{( ) ( ) ( )} 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

Definitie. Se spune că un graf este conex dacă între oricare două vârfuri ale sale există cel

putin un lant care să le lege. În caz contrar graful este neconex.

Un graf se numeste tare conex dacă între oricare două vârfuri ale sale există cel putin un

drum.

Figura 5.1.2.

Exemplu

Graful

Figura 5.1.3a.

este conex, iar graful

Figura 5.1.3b

nu este conex.

Definitie. Gradul unui vârf x se notează g(x) si reprezintă numărul de arce incidente cu

x . Gradul interior al unui vârf x se notează cu g - (x)

si este numărul arcelor de forma

(y, x)ÎG cu y Î X . Gradul exterior al unui vârf x se notează cu g + (x)

si este numărul de

arce de forma (x, y)ÎG cu y Î X .