Para introducirnos en la representación de grafos con maxima vamos a ver primero cómo los representamos.
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
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
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
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\)
Ejercicio: Construir el digrafo del último ejercicio y su matriz de adyacencia.
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. Por cada nodo unido por una arista, ponemos un uno 1 en el lugar correspondiente, y llenamos el resto de las ubicaciones con ceros 0. Un lazo cuenta doble. Si es un digrafo atenderemos como 1 si es un vértice de salida y -1 si es de entrada.
Utilizando la terminología anterior, lamamos matriz de incidencia del grafo no dirigido a la matriz \(|V|\times |E|\), \(M=[m_{ij}]\), donde
\[m_{ij}=\left\{\begin{matrix}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{matrix}\right.\]
Si el grafo es dirigido
\[m_{ij}=\left\{\begin{matrix}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\\ 2 & \mbox{si } \ e_j=(v_i,v_i)\in E\end{matrix}\right.\]
Propiedad: Sean \(\mathbf {A}\) y \(\mathbf {M}\) las matrices de adyacencia e incidencia 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.
Propiedad: Sea \(G(V,E)\) un digrafo cuyo grafo subyacente es simple y \(\mathbf {M}\) su matriz de incidencia, entonces \[rango(M)=|V|-k,\] siendo \(k\) número de componentes conexas del grafo subyacente.
Propiedad: Sean \(\mathbf {A}\) y \(\mathbf {A^\prime}\) son la 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, talque \(A^\prime=PAP^{t}\)
Propiedad: Sea \(\mathbf {A}\) son 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}\) son la matriz de adyacencia de un grafo \(G\), y \(P\), una matriz de permutaciones, talque \(PAP^{t}\) es una matriz diagonal por bloques, entonces:
- El el número de componentes conexas del grafo es igual número de bloques.
- \(G\) es conexo si, y solo si, el número de bloques es 1.
Espectro y laplaciana de un grafo
Sea \(G(V,E)\) un grafo simple y sin bucles con \(|V|=n\) y sea \(A\) la matriz \(n\times n\) de adyacencia del grafo. Como la matriz es real y simétrica, se puede diagonalizar mediante una matriz ortogonal \[A=P\ D\ P^t,\] siendo \(D=diag(\lambda_1,\lambda_2,\ldots,\lambda_n)\), donde \(\lambda_i\) son los autovalores de \(A\). Recordemos que los autovalores se puede repetir.
Definición: Denominamos espectro de una grafo al conjunto de autovalores de su matriz de adyacencia.
Como sabemos de nuestros estudios de Álgebra lineal, podemos considerar \[\lambda_1\geq \lambda_2 \geq \ldots \geq\lambda_n,\] ordenados de mayor a menor. Como la traza de \(A\) es cero, entonces las suma de los autovalores será cero, por tanto habrá positivos y negativos. En concreto, \(\lambda_1>0\) y \(\lambda_n<0\).
Lema: Un grafo es bipartito si y sólo si los autovalores son simétricos respecto al cero; es decir, si λ es autovalor, entonces −λ también lo es.
Otra matriz interesante es la matriz laplaciana de un grafo simple no dirigido.
Definición: Denominamos matriz laplaciana de un grafo simple no dirigido \(G(V,E), \ V=\{v_1, v_2, \ldots, v_n\}\), a la matriz \(\mathcal{L}=[l_{ij}]\) donde \[l_{ij}=\left\{\begin{array}{c,l}grado(v_i) & \mbox{si } i=j\\ -1 & \mbox{si } i\neq j \mbox{ y }\{v_i,v_j\}\in E\\ 0 & \mbox{en otro caso }\end{array}\right.\]
Veamos algunas propiedades interesantes :
Propiedades: Sea un grafo \(G(V,E), \ V=\{v_1, v_2, \ldots, v_n\}\), y \(\mathcal{L}\) su matriz laplaciana, entonces
- \(\mathcal{L}\) es una matriz real, simétrica y semi-definida positiva(todos los valores propios no son inferiores a cero).
- El rango de \(\mathcal{L}\) es \(n-k\) donde \(k\) es el número de componentes conexas de \(G\) .
- Las sumas de las filas y columnas de \(\mathcal{L}\) son zero.
Podemos relacionar la matriz laplaciana de un grafo con su matriz de adyacencia:
Proposición: Sea \(\mathcal{L}\) la matriz laplaciana de un grafo, y \(\mathcal{A}\) su matriz de adyacencia. Sea \(\mathcal{D}\) la matriz diagonal donde \(d_{ii}=\mathbf{gr}(v_i)\), entonces \[\mathcal{L}=\mathcal{D}-\mathcal{A}\]
Ejercicio: Sea G=(V,E), donde V={1,2,3,4,5}, y E={{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {4,5}}. Construir su matriz laplaciana y verificar el resultado anterior.
Más propiedades interesantes:
Proposición: El número de componentes conexas de un grafo G coincide con la multiplicidad del autovalor \(\mu_1= 0\) de su matriz laplaciana
Corolario: si G es un grafo conexo, la multiplicidad del autovalor \(\mu_1= 0\) de la matriz laplaciana de G es 1.
No se define la laplaciana para un digrafo; sin embargo, si \(G(V,E)\) es un digrafo cuyo grafo subyacente es simple y \(\mathbf {M}\) es su matriz de incidencia, entonces \[\mathcal{L}=MM^t.\]
Ejercicio: Dado el digrafo adjunto, ¿cuántos caminos de longitud 3 tiene? |