[Teresarica]

Buenas tardes:

Quisiera saber qué diferenicas hay entre la matriz de incidencia y la de adyacencia al hablar de grafos.

Entiendo que la de incidencia es una matriz con entradas 0 o 1, pero he visto algunos casos con entradas diferentes.

Gracias

[Ignacio Larrosa]

En la matriz de incidencia se representan en las filas los nodos del grafo y en las columnas las aristas, siendo la entrada correspondiente igual a \( 1 \) si el nodo está en la arista y a \( 0 \) si no. Como se puede apreciar se trata de matrices que no son cuadradas.

En las matrices de adyacencia se representan en filas y columnas los nodos del grafo, siendo las entradas el número de aristas que conectan los nodos. Si se trata de un grafo no dirigido, la matriz es simétrica naturalmente. Si se trata de un multigrafo las entradas pueden ser mayores que \( 1 \).

Estas matrices si que son cuadradas. Si se elevan a la potencia n-sima, cada entrada representa el número de caminos de longitud n que conecta cada nodo con otro. En este applet de GeoGebra: Conexión en grafos con recorridos de longitud (menor o) igual a k] se ve esto último.

Saludos,

[Teresarica]

Muchas gracias.

Entiendo que al referirse a la matriz de incidencia, ésta no es "necesariamente" cuadrada ya que puede darse el caso de que el número de nodos sea el mismo que el de aristas, en cuyo caso sí sería cuadrada.

[Ignacio Larrosa]

Muchas gracias.

Entiendo que al referirse a la matriz de incidencia, ésta no es "necesariamente" cuadrada ya que puede darse el caso de que el número de nodos sea el mismo que el de aristas, en cuyo caso sí sería cuadrada.

Si, si, claro. En general no es cuadrada, aunque puede serlo. Pero si no es general, es poco aprovechable que sea cuadrada.

Saludos,

[Teresarica]

Gracias por la aclaración.

Un saludo,