Matrice laplaciana

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

$L=D-A,$

dove D è la matrice di grado e 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\ {\mbox{e}}\ v_{i}{\mbox{ è adiacente a }}v_{j}\\0&{\mbox{altrimenti}}\end{cases}}$

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

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)$