La matriz de incidencia es una de las formas de representación de grafo , en la que se indican los vínculos entre los elementos incidentes del grafo (arista (arco) y vértice). Las columnas de la matriz corresponden a los bordes, las filas corresponden a los vértices. Un valor distinto de cero en una celda de matriz indica la relación entre un vértice y un borde (su incidencia ).
En el caso de un grafo dirigido, cada arco <x,y> se coloca en la columna correspondiente: "1" en la fila del vértice x y "-1" en la fila del vértice y; si no hay conexión entre el vértice y el borde, entonces se pone "0" en la celda correspondiente.
Grafico | Matriz de incidencia |
---|---|
Las filas corresponden a los vértices del 1 al 6 y las columnas corresponden a los bordes e1–e7. Por ejemplo, los de la segunda columna en las filas 2 y 3 significan que la arista e2 conecta los vértices 2 y 3.