Matriz de Incidencia - Definición

Una matriz de incidencia representa las relaciones binarias entre dos elementos,en nuestro caso entre un vértice y una arista del grafo.

Para construir la matriz de incidencia a partir de un grafo debemos realizar una matriz de n x a donde n es el nº de nodos o vértices y a es el nº de aristas.

En esta matriz las columnas representan las aristas y las filas los vértices.

Para cada A[i][j] ,nótese que A es la matriz de Incidencia, puede valer:

0 si vértice i no es incidente con arista j
1 si vértice i es incidente con arista j

Fotografía de un ejemplo de grafo no dirigido y su respectiva matriz de incidencia

Podemos que el nº de unos en una fila nos indican el nº de aristas que inciden en un vértice.