Matriu de adyacencia

Matriu de adyacencia

La matriu de adyacencia és una matriu quadrada que s'utilisa com una forma de representar relacions binarias.

Construcció de la matriu a partir d'un grafo

1. Es crea una matriu zero, les columnes del qual i files representen els nodos del grafo.
2. Per cada aresta que unix a dos nodos, se suma 1 al valor que hi ha actualment en l'ubicació corresponent de la matriu.
   • Si tal aresta és un bucle i el grafo és no dirigit, llavors se suma 1 o 2 (depenent de la convenció usada).
   • Si el grafo és ponderat, llavors en lloc d'un 1 se suma el pes de l'aresta respectiva.

Finalment, s'obté una matriu que representa el número d'arestes (relacions) entre cada parell de nodos (elements).

Existix una matriu de adyacencia única per a cada grafo (sense considerar les permutació de files o columnes), i viceversa.

Eixemples

La següent taula mostra dos grafos i la seua respectiva matriu de adyacencia. Note que en el primer cas, com es tracta d'un grafo no dirigit, la matriu obtinguda és simètrica:

Grafo no dirigit	Matriu de adyacencia
Grafo dirigit	Matriu de adyacencia
Archiu:Grafodirigido.jpg
Grafo ponderat	Matriu de adyacencia
Archiu:Weighted Graph.svg

Propietats de la matriu de adyacencia

• Per a un grafo no dirigit la matriu de adyacencia és simètrica.
• El número de camins C_i,j(k), travessant k arestes des del nodo i al nodo j, ve dau per un element de la potencia k-ésima de la matriu de adyacencia:

Vore també

• Matriu d'incidència
• Matriu laplaciana

Bibliografia

• (2013) Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.