Matriu laplaciana

En teoria de grafos la matriu laplaciana — també denominada matriu de admitancia o matriu de Kirchhoff — és una representació matricial d'un grafo. Un atre tipo de representació matricial la proporciona la matriu de adyacencia, pero la matriu laplaciana és ideal per a realisar la teoria espectral de grafos.

Definició

Donat un grafo G en n nodos, la matriu laplaciana $L:=({\ell }_{i,j}{)}_{n\times n}$ es definix com:

${\ell }_{i,j}:=\{\begin{array}{cc}{\kappa }_i& \text{si}i=j\\ -1& \text{si}i\ne j\text{y}{n}_i\text{ es adyacente a }{n}_j\\ 0& \text{otro caso}.\end{array}$

sent ${\kappa }_i$ el grau del nodo i-ésimo $n_i$. La matriu laplaciana normalisada $ℒ:=({\hat{\ell }}_{i,j}{)}_{n\times n}$ es definix com:

${\hat{\ell }}_{i,j}:=\{\begin{array}{cc}1& \text{si}i=j\text{y}{\kappa }_i\ne 0\\ -\frac{1}{\sqrt{{\kappa }_i{\kappa }_j}}& \text{si}i\ne j\text{y}{n}_i\text{ es adyacente a }{n}_j\\ 0& \text{otro caso}.\end{array}$

Prenent $\hat{T}$ com la matriu diagonal d'elements $(i,i)$ d'entrada ${\kappa }_i$, es té que:

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

en la convenció $({\hat{T}}^{-1}{)}_{v,v}=0$ per a ${\kappa }_v=0$.

Propietats

Relació en la matriu de adyacencias

Quan el grafo $\Gamma$ és k-regular es pot observar que:

$\widehat{ℒ}=\widehat{𝕀}-\frac{1}{k}\hat{A}$

a on $A$ és la matriu de adyacencias i $\widehat{𝕀}$ és l'identitat. Per a un grafo sense vèrtiços aïllats, tenim llavors que:

$\widehat{ℒ}={\hat{T}}^{-1/2}\hat{L}{\hat{T}}^{-1/2}=\widehat{𝕀}-{\hat{T}}^{-1/2}\hat{A}{\hat{T}}^{-1/2}$.

Eixemple

Eixemple de la representació en forma de grafo d'una ret i la seua representació matricial laplaciana:

grafo	matriu laplaciana
Archiu:6n-graf.svg	$\left(\begin{array}{cccccc}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)$

Espectre de $\widehat{ℒ}$

Per a un grafo $\Gamma$ i matriu laplaciana $L(\Gamma )$, en els autovalorés ordenats (l'espectre de $L$) ${\lambda }_0⩽{\lambda }_1⩽\dots ⩽{\lambda }_{n-1}$:

1. La matriu laplaciana és sempre semidefinida positiva.
2. El primer autovalor ${\lambda }_0=0$ és sempre nul; existix un autovector que és sempre $[1,1,\dots ,1]$. La multiplicitat de ${\lambda }_0$ indica el número de subgrafos inconexos que hi ha.
3. El segon autovalor no nul ${\lambda }_2$ es denomina conectivitat algebraica. És una mida de la conectivitat del grafo. A mida que ${\lambda }_2$ es fa més chicotet el grafo adquirix una estructura més modular. A través de la percolación a través d'un grafo, la sincronisació màxima es dona per al valor més alt possible de ${\lambda }_2$. També es denomina bot espectral, gap o paràmetro de Fiedler.

Vore també

• Model en grafo
• Algoritme de Floyd
• Relació social
• Iconografia de les correlació