Matrice de adiacenta

Matricea de adiacentă 

Fie G=(V; U) un graf orientat cu n vârfuri (V={ 1,2, ..., n}) şi m arce.
Matricea de adiacentă (A∈Mn({0,1})), asociată grafului G, este o matrice pătratică de ordin n, cu
elementele:

 (altfel spus, ai,j=1, dacă există arc între i şi j şi ai,j=0 dacă nu există arc între i şi j. )

• Exemplul 1.                                                         • Exemplul 2. 

Fie graful reprezentat ca în figura de mai jos:           Fie graful reprezentat ca în figura de mai jos:

* Comentarii: 

l. Matricea de adiacenŃă este o matrice pătratică, de ordin n, şi nu este neapărat simetrică faŃă de diagonala 

principală, aşa cum este în cazul grafurilor neorientate. 

Matricea vârfuri-arce ( matricea de incidentă) 

 

Fie G=(V, U) un graf orientat cu n vârfuri (V={1,2, ..., n}) şi m arce. 

Matricea vârfuri-arce (B∈Mnxm({-1,0,1})), asociată grafului G, este o matrice cu n linii şi m coloane, cu 

elementele:

• Exemplul 1. Fie graful G=(V,U) : 

V={1,2,3,4}, 

U={(1,3),(2,3),(2,4),(4,1)}= {u1, u2, u3, u4}