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{array}{cc}\mathrm{deg}(v_i)& \text{se}i=j\\ -1& \text{se}i\ne j\wedge v_i,v_j\text{ adiacenti}\\ 0& \text{altrimenti}\end{array}$

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}{cccccc}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}{cccccc}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}{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)$

Collegamenti esterni

• Template:Collegamenti esterni