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
Top Related