Capítulo 11 “Matriz de Incidencia”

Sea G = (V,A) un grafo con n vértices y m aristas, llamamos matriz de incidencia a la matriz de orden n x m, rellenaremos la matriz con los siguientes datos:

Cada columna corresponderá a una arista y cada fila a un vértice.

GRAFOS NO DIRIGIDOS

0 si Vi no es incidente con la Aj
1 si Vi es incidente con la Aj
2 si Aj es un bucle en Vi

Cada columna sumará 2 ya que toda arista es incidente con 2 vértices

La suma de los elementos de cada fila corresponde al grado de cada vértice

GRAFOS DIRIGIDOS

0 si Vi no es incidente con la Aj
1 si Vi es vértice inicial de Aj
-1 si Vi es vértice final de Aj
2 si Aj es un bucle en Vi

Cada columna sumará 0 o 2, ya que cada arco cuando empieza ponemos 1 y cuando acaba -1 por lo tanto vuelve a ser 0 si es un bucle entonces es 2

Ejemplo

Grafo C	Grafo D