Matriz laplaciana
# Matriz laplaciana

En teoría de grafos la matriz laplaciana — también denominada matriz de admitancia o matriz de Kirchhoff — es una representación matricial de un grafo. Otro tipo de representación matricial la proporciona la matriz de adyacencia, pero la matriz laplaciana es ideal para realizar la teoría espectral de grafos.

## Definición

Dado un grafo G con n nodos, la matriz laplaciana $L:=(\ell _{i,j})_{n\times n}$ se define como:

    $\ell _{i,j}:={\begin{cases}\kappa _{i}&{\mbox{si}}\ i=j\\-1&{\mbox{si}}\ i\neq j\ {\mbox{y}}\ n_{i}{\mbox{ es adyacente a }}n_{j}\\0&{\mbox{otro caso}}.\end{cases}}$

siendo $\kappa _{i}$ el grado del nodo i-ésimo $n_{i}$. La matriz laplaciana normalizada ${\mathcal {L}}:=({\hat {\ell }}_{i,j})_{n\times n}$ se define como:

    ${\hat {\ell }}_{i,j}:={\begin{cases}1&{\mbox{si}}\ i=j\ {\mbox{y}}\ \kappa _{i}\neq 0\\-{\frac {1}{\sqrt {\kappa _{i}\kappa _{j}}}}&{\mbox{si}}\ i\neq j\ {\mbox{y}}\ n_{i}{\mbox{ es adyacente a }}n_{j}\\0&{\mbox{otro caso}}.\end{cases}}$

Tomando ${\hat {T}}$ como la matriz diagonal de elementos $(i,i)$ de entrada $\kappa _{i}$, se tiene que:

    ${\hat {\mathcal {L}}}={\hat {T}}^{-1/2}{\hat {L}}{\hat {T}}^{-1/2}$

con la convención $({\hat {T}}^{-1})_{v,v}=0$ para $\kappa _{v}=0$.

## Propiedades

### Relación con la matriz de adyacencias

Cuando el grafo $\Gamma$ es k-regular se puede observar que:

    ${\hat {\mathcal {L}}}={\hat {\mathbb {I} }}-{\frac {1}{k}}{\hat {A}}$

donde $A$ es la matriz de adyacencias y ${\hat {\mathbb {I} }}$ es la identidad. Para un grafo sin vértices aislados, tenemos entonces que:

    ${\hat {\mathcal {L}}}={\hat {T}}^{-1/2}{\hat {L}}{\hat {T}}^{-1/2}={\hat {\mathbb {I} }}-{\hat {T}}^{-1/2}{\hat {A}}{\hat {T}}^{-1/2}$.

### Ejemplo

Ejemplo de la representación en forma de grafo de una red y su representación matricial laplaciana:

| grafo | matriz laplaciana |
| - | - |
| | $\left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{array}}\right)$ |

### Espectro de ${\hat {\mathcal {L}}}$

Para un grafo $\Gamma$ y matriz laplaciana $L(\Gamma )$, con los autovalores ordenados (el espectro de $L$) $\lambda _{0}\leqslant \lambda _{1}\leqslant \dotsc \leqslant \lambda _{n-1}$:

* La matriz laplaciana es siempre definida positiva.
* El primer autovalor $\lambda _{0}=0$ es siempre nulo; existe un autovector que es siempre $[1,1,\dots ,1]$. La multiplicidad de $\lambda _{0}$ indica el número de subgrafos inconexos que hay.
* El segundo autovalor no nulo $\lambda _{2}$ se denomina conectividad algebraica. Es una medida de la conectividad del grafo. A medida que $\lambda _{2}$ se hace más pequeño el grafo adquiere una estructura más modular. A través de la percolación a través de un grafo, la sincronización máxima se da para el valor más alto posible de $\lambda _{2}$. También se denomina salto espectral, gap o parámetro de Fiedler.
