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.
Matriz Laplaciana en Digrafos
La forma más común de definirla utiliza la matriz de grados de salida ($D_{out}$). Si tenemos un digrafo $G = (V, E)$, la matriz laplaciana $\mathcal{L}$ se define como:$$\mathcal{L} = D_{out} – A$$
Donde:
- $D_{out}$: Es una matriz diagonal donde cada elemento de la diagonal $d_{ii}$ es el número de aristas que salen del nodo $i$.
- $A$: Es la matriz de adyacencia del digrafo, donde $A_{ij} = 1$ si existe un arco del nodo $i$ al nodo $j$, y $0$ en caso contrario.
Propiedades
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.
Propiedad: Sea y \(\mathbf {B}\) las matrices de incidencia (orientada) de un grafo o digrafo \(G(V,E)\), entonces \[\mathcal{L}=BB^t.\]
| Ejercicio: Dado el digrafo adjunto, ¿cuántos caminos de longitud 3 tiene?
|
