Matriz de Adyacencia- Definición

La Matriz de Adyacencia representa relaciones binarias,en este caso entre dos nodos de un grafo.

Esta matriz es cuadrada puesto que las columnas y filas representan los nodos o vértices del grafo.

Cada A[i][j] representa si existe una arista que una i,j nodo

0 si i y j no tiene arista que los relacione
1 si i y j si tiene arista que los relacione
2 si i=j y existe arista,bucle

Ejemplo De grafo no dirigido y su respectiva Matriz adyacencia ,podemos observar que la matriz es simétrica por ser no dirigido. 

En un grafo dirigido ocurre que:

La suma de los valores de la columna nos da el grado de entrada del nodo que la "proyecta".
La suma de los valores de la fila  nos da el grado de salida del nodo que la "proyecta".

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.