Matrice laplaciana

Dato un grafo semplice G con n vertici, la sua matrice Laplaciana $\mathbf {L} :=(\ell _{i,j})_{n\times n}$ è definita come:

$\mathbf {L} =\mathbf {D} -\mathbf {A} ,$

dove $\mathbf {D}$ è la matrice di grado e $\mathbf {A}$ è la matrice delle adiacenze del grafo.

In caso di grafi orientati, sia il numero di archi in uscita o in entrata può essere usato.

Dalla definizione segue che:

$\ell _{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{se}}\ i=j\\-1&{\mbox{se}}\ i\neq j\ \land \ v_{i},v_{j}{\mbox{ adiacenti}}\\0&{\mbox{altrimenti}}\end{cases}}$

dove deg(v_i) è il grado del vertice i.

Tale nozione può essere generalizzata al caso di grafi rappresentati da matrici di adiacenza pesata $\mathbf {W}$, con $w_{ij}\geq 0$, con matrici di grado $\mathbf {D}$.

Esempio

Esempio di un grafo semplice e la sua matrice Laplaciana.

Grafo semplice	Matrice di grado	Matrice di adiacenza	Matrice Laplaciana
	$\left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)$	$\left({\begin{array}{rrrrrr}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{array}}\right)$	$\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)$

Collegamenti esterni

• (EN) Eric W. Weisstein, Laplacian Matrix, su MathWorld, Wolfram Research.