MAD: Representación matricial de un grafo

Matriz de adyacencia

Si tenemos un grafo \(G=(V,E)\) donde \(V=\{v_1,…,v_n\}\), llamamos matriz de adyacencia del grafo a la matriz cuadrada nxn, \(A=[a_{ij}]\), donde
\[a_{ij}=\left\{\begin{matrix}1 & \mbox{si } \{v_i,v_j\}\in E\\ 0 & \mbox{si } \{v_i,v_j\}\not\in E\end{matrix}\right.\]

Si tenemos un digrafo \(G=(V,E)\) donde \(V=\{v_1,…,v_n\}\), llamamos matriz de adyacencia del digrafo a la matriz cuadrada nxn, \(A=[a_{ij}]\), donde \[a_{ij}=\left\{\begin{matrix}1 & \mbox{si } (v_i,v_j)\in E\\ 0 & \mbox{si } (v_i,v_j)\not\in E\end{matrix}\right.\]

Para ambos casos, si hubiera un bucle en \(v_i\) \(a_{ii}\) es 1 (dependiendo de la convención usada, también puede aparecer 2).

Ejercicio: Determinar la matriz de adyacencia del grafo

Solución:

Ejercicio: Crear una función en maxima que, dada una lista de aristas, nos devuelva su matriz de adyacencia.

Solución:

Veamos algunas propiedades interesantes

Propiedades: La matriz de adyacencia, \(A\), verifica:

• es simétrica para un grafo no dirigido;
• Depende del etiquetado del grafo. Existe una correspondencia biyectiva entre los grafos simples etiquetados con \(n\) vértices y las matrices \(n\times n\) simétricas binarias con ceros en la diagonal.
• no es binaria para un multigrafo.
• para un pseudografo, la diagonal principal no está formada únicamente por ceros.
• si un grafo tiene un vértice \(v_i\) aislado, tanto la columna \(i-ésima\) de \(A\) como la fila \(i-ésima\) estarán formadas por ceros.
• si \(G\) es un grafo no dirigido, la suma de los elementos de la fila (o columna) \(i-ésima\) de \(A\) coincide con el grado del vértice \(v_i\).
• en un grafo no dirigido sin lazos, la suma de todos los elementos es el doble del tamaño del grafo, es decir, el doble del número de aristas del grafo. En grafos dirigidos, la suma de todos los elementos de \(A\) da exactamente el tamaño del grafo

Observar que una de las propiedades nos decía que, en un grafo no dirigido, la suma de los elementos de la fila (o columna) \(i-ésima\) de \(A\) coincide con el grado del vértice \(v_i\). En general, podríamos decir que si \(A\) es la matriz de adyacencia de un grafo y \(\mathbf{1}\) es la matriz columna de tantas filas como orden tiene \(A\), el producto \[\mathbf{d}=A.\mathbf{1}\] nos proporciona los grados de cada uno de los vértices del grafo.

Si tenemos un digrafo \[\mathbf{d}_{out}=A.\mathbf{1}\] el vector de grados de salida.

Caminos y distancia

Otra propiedad interesante es la posibilidad de conocer los caminos de un vértice a otro. Si llamamos \(C_{ij}(k)\) el número de caminos de longitud \(k\) entre los vértices \(v_i\) y \(v_j\), este se puede determinar mediante la potencia \(k\)-ésima de la matriz de adyacencia. Es decir, si \(\mathbf {A}=[a_{ij}]\) es la matriz de adyacencia, \[C_{i,j}(k)=[\mathbf{A}^{k}]_{ij}.\]

Ejercicio: Cuántos caminos de longitud 4 parten del vértice 1 del grafo anterior

Solución:

Ejercicio: Sea \(G(V,E)\), siendo \(E:\{\{1,4\},\{1,2\},\{2,2\},\{1,3\},\{2,3\}\}\) ¿Qué dos vértices no están conectados por una camino de longitud 2?

Solución:

Ejercicio: Sea \(G(V,E)\), siendo \(E:\{\{1,4\},\{1,2\},\{2,2\},\{1,3\},\{2,3\}\}\) ¿Cuántos caminos de longitud 3 hay?

Solución:

Cuando el grafo es simple, esta potencia nos sirve para ver el grado de cada vértice:
\[grado(v_i)=[\mathbf{A}^{2}]_{ii}.\]

Y como sabemos que \(\sum_{v\in V} grado(v)=2|E|\), tendremos \[|E|=\frac{1}{2}traza(\mathbf{A}^{2}).\]

La tercera potencia también nos proporciona datos curiosos.

Propiedad: Si \(\mathbf {A}=[a_{ij}]\) es la matriz de adyacencia de un grafo \(G\), el número de triángulos (circuitos de longitud 3)

• del grafo es \[\frac{1}{6}traza(\mathbf{A}^{3})\]
• que tienen a \(v_i\) como vértice es \[\frac{1}{2}\left[\mathbf{A}^{3}\right]_{ii}\]

Ejercicio: Cuántos triángulos tiene el grafo completo \(K_5\)

Solución:

Ejercicio: ¿Cuántos caminos de longitud 5 tiene el digrafo?

Solución:

Proposición: El diámetro de un grafo es el valor $k$ más pequeño necesario para que la matriz sumatoria de potencias, de su matriz de adyacencia, no tenga ceros.

Isomorfismos y adyacencia

Propiedad: Sean \(\mathbf {A}\) y \(\mathbf {A^\prime}\) las matrices de adyacencia de los grafos \(G\) y \(G^\prime\), entonces las siguientes condiciones son equivalentes:

• \(G\equiv G^\prime\) (isomorfos)
• Existe una matriz \(P\), matriz de permutaciones, tal que \(A^\prime=PAP^{t}\)

Propiedad: Sea \(\mathbf {A}\) la matriz de adyacencia de un grafo \(G(V,E)\), con \(|V|=n\), entonces las siguientes condiciones son equivalentes:

• \(G\) es conexo
• son mayores que cero las entradas de la matriz \[I_{n}+A+A^{2}+A^{3}+\ldots+A^{n-1}\]

Propiedad: Sea \(\mathbf {A}\) la matriz de adyacencia de un grafo \(G\), y \(P\), una matriz de permutaciones, tal que \(PAP^{t}\) es una matriz diagonal por bloques; entonces:

1. El número de componentes conexas del grafo es igual número de bloques.
2. \(G\) es conexo si, y solo si, el número de bloques es 1.

Matriz de incidencia

Del mismo modo podemos construir la matriz de incidencia, donde las columnas de la matriz representan las aristas del grafo y las filas representan a los distintos nodos.

Grafo no dirigido

Utilizando la terminología anterior, llamamos matriz de incidencia del grafo no dirigido a la matriz \(|V|\times |E|\), \(M=[m_{ij}]\), donde
\[m_{ij}=\left\{\begin{array}{ll}0 & \mbox{si } \not\exists v\in V|\ e_j=\{v_i,v\}\in E\\ 1 & \mbox{si } \exists v\in V|\ e_j=\{v_i,v\}\in E\\ 2 & \mbox{si } \ e_j=\{v_i,v_i\}\in E\end{array}\right.\]

Grafo dirigido

\[m_{ij}=\left\{\begin{array}{ll}0 & \mbox{si } \not\exists v\in V|\ e_j=(v_i,v)\in E\\ 1 & \mbox{si } \exists v\in V|\ e_j=(v_i,v)\in E\\ -1 & \mbox{si } \exists v\in V|\ e_j=(v,v_i)\in E\end{array}\right.\]
Observar que un bucle entra y sale del mismo vértice, luego contribuye +1 y −1, por tanto es cero.

Ejercicio: ¿Cuál es la norma de la matriz de incidencia del digrafo?

Solución:

Ejercicio: Crear una función en maxima que, dada una lista de aristas, nos devuelva su matriz de incidencia.

Solución:

Matriz de incidencia y conexión

La matriz de incidencia nos permite conocer las componentes conexas de un grafo.

Propiedad: Sea \(\mathbf{M}\) la matriz de incidencia de un digrafo \(G(V,E)\), con \(|V|=n\), entonces \[\mathbf{rang}(M)=n-c\] siendo \(c\) el número de componentes conexas del digrafo.

Observar que hemos dado esta propiedad para un digrafo. Del mismo modo podemos establecerla para un grafo no dirigido, pero en este caso es más sencillo si orientamos artificialmente el grafo.

Definición: \(G(V,E)\) un grafo no dirigido; llamaremos matriz de incidencia orientada B del grafo \(G(V,E)\) a la matriz de incidencia resultante de darle una orientación a las aristas del grafo. Es decir, lo transformamos en un digrafo.

Esta orientación es arbitraria, no modifica las propiedades algebraicas que nos interesan del grafo y nos permite interpretarlas de una forma más sencilla. Por ejemplo, ahora podemos repetir la propiedad anterior:

Propiedad: Sea \(\mathbf{B}\) la matriz de incidencia orientada de un grafo \(G(V,E)\), con \(|V|=n\), entonces \[\mathbf{rang}(B)=n-c\] siendo \(c\) el número de componentes conexas del grafo.

Si tenemos un digrafo, la matriz \(\mathbf{B}\) (matriz de incidencia orientada) es la misma, ya que el digrafo está orientado.

Matriz de incidencia y adyacencia

Propiedad: Sean \(\mathbf {A}\) y \(\mathbf {B}\) las matrices de adyacencia e incidencia (orientada) de un grafo o digrafo \(G(V,E)\), entonces \[D-A=BB^t,\] siendo \(D\) una matriz diagonal cuyos elementos de la diagonal son los grados de los vértices correspondientes.

Para obtener la matriz de grados ($D$) a partir de la matriz de adyacencia ($A$), la forma más eficiente y universal, válida tanto para grafos dirigidos como no dirigidos, es multiplicar la matriz $A$ por un vector columna de unos ($\mathbf{1}$), el resultado es un vector donde cada componente es la suma de la fila correspondiente.

Para un grafo de $n$ nodos, sea $\mathbf{1} = [1, 1, \dots, 1]^T$:$$\mathbf{d} = A\mathbf{1}$$ donde $\mathbf{d}$ es el vector de grados. Para convertir este vector en la matriz diagonal $D$, usamos el operador $\text{diag}$: $$D = \text{diag}(A\mathbf{1})$$

Ejercicio: Dado el grafo adjunto, verificar la relación anterior.

Solución:

Si el grafo es simple, tendríamos:

Propiedad: Sean \(\mathbf {A}\) y \(\mathbf {M}\) las matrices de adyacencia e incidencia (no orientada) de un grafo simple \(G(V,E)\), entonces \[A+D=MM^t,\] siendo \(D\) una matriz diagonal cuyos elementos de la diagonal son los grados de los vértices correspondientes.

Solución: