Una matriz de incidencia relaciona directamente vértices con aristas: cada fila representa un vértice y cada columna representa una conexión concreta del grafo.
La matriz de adyacencia compara pares de vértices. La matriz de incidencia utiliza un enfoque diferente: sus filas representan vértices y sus columnas representan aristas.
Cada columna indica qué vértices participan en una conexión. Esta representación conserva la identidad individual de las aristas, por lo que puede resultar útil para multigrafos, redes de flujo y operaciones algebraicas.
Un grafo con n vértices y m aristas produce una matriz de n filas y m columnas.
A diferencia de la matriz de adyacencia, no tiene por qué ser cuadrada.
En un grafo no dirigido simple, cada columna contiene un 1 en las filas correspondientes a los dos extremos de la arista y 0 en las demás.
Si e₁ = {A, B}, su columna contiene un 1 en A y otro en B.
En grafos dirigidos se utiliza con frecuencia una matriz orientada: el origen recibe −1 y el destino recibe +1.
| Relación con el arco | Valor |
|---|---|
| El vértice es el origen | −1 |
| El vértice es el destino | +1 |
| El vértice no participa | 0 |
Algunas fuentes utilizan la convención opuesta. Lo importante es documentar la elegida y aplicarla de forma consistente.
Selecciona dos vértices para agregar o quitar una arista. Cada nueva conexión crea una columna. En modo dirigido, el primer vértice es el origen y el segundo es el destino.
Matriz de incidencia
1 = vértice incidente
Observa que agregar una arista aumenta el número de columnas, pero no el de filas. Al cambiar a modo dirigido, las conexiones mantienen sus extremos y muestran su orientación mediante signos.
En un grafo simple no dirigido sin bucles, cada columna suma 2 porque posee exactamente dos valores 1.
Estas propiedades permiten verificar rápidamente si una matriz respeta la convención utilizada.
Podemos crear una fila por vértice y una columna por arista, e indicar los extremos con 1.
function matrizIncidencia(vertices, aristas) {
return vertices.map(vertice =>
aristas.map(([a, b]) =>
vertice === a || vertice === b ? 1 : 0
)
);
}
const vertices = ["A", "B", "C"];
const aristas = [["A", "B"], ["A", "C"]];
console.log(matrizIncidencia(vertices, aristas));Para arcos dirigidos asignamos −1 al origen y +1 al destino.
function matrizOrientada(vertices, arcos) {
return vertices.map(vertice =>
arcos.map(([origen, destino]) => {
if (vertice === origen) return -1;
if (vertice === destino) return 1;
return 0;
})
);
}
console.log(matrizOrientada(
["A", "B", "C"],
[["A", "B"], ["C", "A"]]
));En un grafo no dirigido sin bucles, sumar la fila de un vértice produce su grado. En una matriz orientada, los signos permiten distinguir entradas y salidas.
| Matriz | Operación sobre una fila | Resultado |
|---|---|---|
| No dirigida | Contar valores 1 | Grado |
| Orientada | Contar valores −1 | Grado de salida |
| Orientada | Contar valores +1 | Grado de entrada |
La matriz de incidencia conserva una columna independiente para cada arista. Por eso representa naturalmente varias conexiones entre los mismos vértices.
Las columnas pueden ser idénticas, pero siguen correspondiendo a aristas diferentes.
| Representación | Filas | Columnas | Espacio típico |
|---|---|---|---|
| Lista de adyacencia | Vértices | No aplica | O(V + E) |
| Matriz de adyacencia | Vértices | Vértices | O(V²) |
| Matriz de incidencia | Vértices | Aristas | O(V × E) |
La matriz de incidencia describe qué vértices participan en cada arista. Aunque puede consumir más memoria que una lista de adyacencia, resulta valiosa cuando las conexiones deben tratarse como objetos independientes.
En el próximo tema estudiaremos con mayor profundidad el grado de un vértice y sus propiedades.