Arreglo bidimensional que representa un grafo finito cuyo elemento (i,j) registra la presencia y, posiblemente, el peso de una arista entre el nodo i y el nodo j.

Principio

Codificar la conectividad discreta en un objeto de álgebra lineal para que las operaciones sobre el grafo se traduzcan en operaciones matriciales.

Demostración

Para un grafo simple no dirigido con nodos {1,2,3,4} y aristas {1–2,2–3,3–4}, la matriz de adyacencia A tiene ceros en la diagonal y unos en las posiciones (1,2),(2,1),(2,3),(3,2),(3,4),(4,3).

Aplicación incorrecta

Tratar la misma matriz de adyacencia como descriptor completo de un multigrafo sin ampliar las entradas a recuentos provoca pérdida de la información de multiplicidad.

Consecuencia

Permite usar álgebra matricial (potencias, productos, cálculos de índices) para estudiar recorridos, conectividad y propiedades combinatorias del grafo.

Inversión

Una matriz de incidencia registra en cambio las incidencias nodo–arista en lugar de conexiones nodo–nodo, cambiando el enfoque de la adyacencia a la pertenencia a aristas.

Límite

Definida para grafos finitos; para hipergráfos, redes multilayer o estructuras con aristas etiquetadas, la adyacencia binaria básica debe ampliarse o reemplazarse.

Tensión semántica

Frente a una adyacencia ponderada: la matriz de adyacencia sin calificar conlleva con frecuencia entradas binarias, mientras que muchos análisis requieren valores reales.

Síntesis

Una matriz compacta cuyo patrón de entradas es una codificación directa en álgebra lineal de qué nodos están conectados y con qué intensidad en un grafo finito.