Matrice laplaciana

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

${\displaystyle 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:

${\displaystyle \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.

Esempio

Esempio di un grafo semplice e la sua matrice Laplaciana.

Grafo semplice	Matrice di grado	Matrice di adiacenza	Matrice Laplaciana
	${\displaystyle \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)}$	${\displaystyle \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)}$	${\displaystyle \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)}$

Note

1. MathWorld.

Collegamenti esterni

• (EN) Eric W. Weisstein, Matrice laplaciana, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica