Reprezentarea grafurilor orientate

Pentru reprezentarea grafurilor orientate se poate folosi:

Matricea de adiacenta;Matricea varfuri-arce;Liste de adiacenta;Vectorul de arce;

Matricea de adiacenta Pentru un graf cu n varfuri , matricea

de adiacenta este patratica,nesimetrica ,ale carei elemente se definesc astfel:

aij=..a) 1, daca exista arc de la i la j (i,j);b) 0, daca nu exista arc de la i la j ; 0 0 1 1 0 0 0 0 0 0 A= 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0

1

5 2

4

3

Vectorul de muchii

Pentru un graf cu n varfuri

si m arce , vectorul de arce are

ca numar de componente

valoarea m . Fiecare element al

sau fiind un arc care va

reprezenta extremitatea initiala

si cea finala.

V={(1,2),(1,3),(2,3),

(4,1),(4,2)}

1

2

43

Matricea varfuri-arce Se face printr-o matrice

B,cu n linii (-varfuri) si m coloane(-arce),in care componenta este reprezentata astfel :bij=

1 , daca varful i este extremitate initiala a arcului Uj;

-1, daca varful i este extremitate finala a arcului Uj;

0, daca nu exista arcul;

V={(1,2),(1,4),(2,3),(2,5),(3,1),(4,3),(5,4)} u1 u2 u3 u4 u5 u6 u7 1 1 0 0 -1 0 0 -1 0 1 1 0 0 0 B= 0 0 -1 0 1 -1 0 0 -1 0 0 0 1 -1 0 0 0 -1 0 0 1

1

2

3

4 5

Liste de adiacenta Pentru fiecare varf se construiesc

doua liste : L+(x) : reprezinta lista vecinilor succesori

care contine varfurile ce sunt extremitatile finale ale arcelor care ies din varful x;

L-(x) : reprezinta lista vecinilor predecesori care contine varfurile ce sunt extremitatile initiale ale arcelor care intra in varful x;

Vf-x L+(x) L-(x)

1 2 5

2 ø 1,3

3 2 4,5

4 3,5 ø

5 1,3 4

1

35

4

2