Matriu d'adjacència

La 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, es 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 es 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 graf s. 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 .

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Matriu d'adjacència