Matricea de adiacenta. -P.D.

Matricea de adiacenta este o matrice a cu n linii si n coloane, in care elementele a[i,j] se definesc astfel:

• 1, daca exista muchia [i,j] cu i diferit de j. 
• 0 in caz contrar. 

Lista vecinilor nodului x cuprinde toate nodurile care sunt extremitati ale muchiilor ce trec prin nodul x.

Observatii:

•         Matricea de adiacenta asociatã unui graf neorientat este o matrice simetricã
•          Suma elementelor de pe linia k reprezintã gradul nodului k
•          Suma elementelor de pe coloana k reprezintã gradul  nodului k

Fie graful din figura urmatoare: 

                                                                          
                                 0 1 0 1 0 0           nodul 1 are gradul 2
                                 1 0 1 0 0 0           nodul 2 are gradul 2
                                 0 1 0 1 1 0           nodul 3 are gradul 3
                                 1 0 1 0 0 0           nodul 4 are gradul 4
                                 0 0 1 0 0 0           nodul 5 are gradul 1
                                 0 0 0 0 0 0           nodul 6 are gradul 0       

• Numarul de noduri este 6 si numarul de muchii este 5.
• Matricea este simetrica si patratica avand 6 linii si 6 coloane.
• Diagonala principala contine numai valori nule.

Pentru a prelucra graful se citesc:

6- reprezentand n, numarul de noduri
5- reprezentand m, numarul de muchii
5 perechi x-y reprezentand extremitatile celor 5 muchii:

1-2 => a[1,2]=a[2,1]=1
1-4 => a[1,4]=a[4,1]=1
2-3 => a[2,3]=a[3,2]=1
3-4=>  a[3,4]=a[4,3]=1
3-5 => a[3,5]=a[5,3]=1
 
Matricea de adiacenta este o matrice patratica si simetrica fata de diagonala principala.
 
Exemplu de matrice patratica: