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
- Es crea una matriu zero, les columnes i files representen els nodes del graf.
- 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
La matriu d'adjacència per al graf de la figura ve donada per:
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:
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 .