Matriu d'adjacència

Una matriu d'adjacència és una matriu quadrada que s'utilitza com una forma de representar relacions binàries.

Construcció de la matriu a partir d'un graf

1. Es crea una matriu zero, les columnes i files representen els nodes del graf.
2. Per cada aresta que uneix dos nodes, se suma 1 al valor que hi ha actualment en la ubicació corresponent de la matriu.

   Si aquesta aresta és un bucle i el graf és no dirigit, llavors se suma 2 en comptes de 1.

Finalment, s'obté una matriu que representa el nombre d'arestes (relacions) entre cada parell de nodes (elements).

Hi ha una matriu d'adjacència única per a cada graf (sense considerar les permutacions de files o columnes), i viceversa.

Exemple

Exemple de graf, per al qual es calcula la matriu d'adjacència.

La matriu d'adjacència per al graf de la figura ve donada per:

$\mathbf {A} ={\begin{bmatrix}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{bmatrix}}$

Propietats de la matriu d'adjacència

• Per a un graf no dirigit la matriu d'adjacència és simètrica.
• El nombre de camins C _{i, j} (k), travessant k arestes des del node i al node j, ve donat per un element de la potència k -èsima de la matriu d'adjacència:

$C_{i,j}(k)=[\mathbf {A} ^{k}]_{ij}$

Comparació amb altres representacions

Hi ha altres formes de representar relacions binàries, com ara els parells ordenats o els grafs. Cada representació té les seves prestacions. En particular, la matriu d'adjacència és molt utilitzada en la programació informàtica, perquè la seva naturalesa binària i matricial calça perfecte amb la dels ordinadors. No obstant això, una persona normal i corrent se li farà molt més senzill comprendre una relació descrita mitjançant grafs, que mitjançant matrius d'adjacència. Una altra representació matricial per a les relacions binàries és la matriu d'incidència.

Aplicacions

La relació entre un graf i el vector i valor propi de la seva corresponent matriu d'adjacència s'estudien en la teoria espectral de grafs .