Matriu d'adjacència

De Viquipèdia
Dreceres ràpides: navegació, cerca

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[modifica | modifica el codi]

  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[modifica | modifica el codi]

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[modifica | modifica el codi]

  • 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[modifica | modifica el codi]

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[modifica | modifica el codi]

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 Modifica l'enllaç a Wikidata