Introducere Elementară în Teoria Grafurilor

1: Reprezentări ale unui graf

Un graf este o pereche G = ( A , V ) formată din :

• mulţimea finită V , numită “ mulţime de vârfuri “ : un element

se numeşte “ vârf “ al grafului G ;

• mulţimea numită “ mulţime de arce “: un element

se numeşte “ arc “ al grafului G.

EXEMPLU : fie V = { a , b , c , d } şi A = { ( a,b) , (d,c) , (b,c) , ( c,a) } .

Graful G = ( A , V ) poate fi reprezentat schematic astfel :

Mai importante sunt reprezentările matriceale ale grafurilor : vom prezenta în continuare unele reprezentări mai utilizate .

Fie graful G = ( A , V ) , cu | V | = n .

Matricea latină L(G) = || sij || , i,j = 1,n este un tablou alfanumeric ,având elementele

sij date de

Pentru graful din exemplul precedent , avem

L(G) =

a b c d

a * (a,b) * (a,d)

b * * (b,c) *

c (c,a) * * *

d * * (d,c) *

Matricea binară sau booleană X(G) = || xij || , i,j = 1,n are elemente de “0” şi “1” aparţinând lui Z2 , asociate astfel :

Pentru graful G din exemplul precedent avem :

X(G) =

a b c d

a 0 1 0 1

b 0 0 1 0

c 1 0 0 0

d 0 0 1 0

Matricea X(G) se numeşte “ matricea arcelor “ grafului G.

= 2 :Noţiuni introductive :

Fie graful G = ( A , V ) , cu | V | = n .

• pentru arcul , vârful a se numeşte “ sursa “ arcului , iar vârful

b se numeşte “ destinaţia “ arcului ; vom spune că arcul este un arc

“ de la a la b “

• un drum elementar de lungime k , , în graful G = ( A , V ) este o succesiune

de arce , cu proprietatea că destinaţia fiecărui arc este aceeaşi cu sursa arcului

următor

EXEMPLU: în graful G deja prezentat , drumul d = { ( a, b ) , ( b , c ) , ( c, a ) }

este un drum elementar de lungime 3

Acest drum scris ca o listă de arce , d = { (a,b) , (b,c) , (c,a) }se mai poate scrie ca o

listă de vârfuri d = { a , b , c , a }.

Observare : un drum elementar se zice că :

• are ca sursă , sursa primului arc , a , şi ca destinaţie , destinaţia ultimului arc , b , sau că este un drum “ de la a la b “.

• drumul f « trece « prin vârfurile arcelor care îl compun .

= 3 : Matricea drumurilor într-un graf

Fie graful G = ( A , V ) , cu V = { v1 , v2 , … , vn } .

Urmărim să construim matricile următoare :

• pentru fiecare , matricea , numită « matricea drumurilor

de lungime « k » a grafului G , unde avem :

• , dacă în G există un drum de lungime “k” de la vi la vj ;

• , dacă în G nu există nici un drum de lungime “k” de la vi la vj .