Matriz de incidencia
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.
Ejemplo
| 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.
Características de esta representación
- Se utiliza para cualquier gráfico, incluso si hay un bucle.
- Cada columna debe contener como máximo dos 1 (si este borde es un bucle, entonces el 1 se coloca frente al vértice al que incide el bucle). En el caso de un gráfico dirigido, la columna debe contener 1 y -1.
- Puede usarse para representar hipergrafías (en cuyo caso la columna puede contener más de dos 1)
Véase también
Notas
Literatura
- Harari F. Teoría de grafos. — M.: Mir. - 1973. - 300 págs.