Laplacian matrix

Laplacian matrix --- лапласиан.

Let [math]\displaystyle{ G }[/math] be a simple graph on [math]\displaystyle{ n }[/math] vertices. Let [math]\displaystyle{ deg_{i} }[/math] denote the degree of a vertex [math]\displaystyle{ v_{i} }[/math], [math]\displaystyle{ i = 1,2, \ldots, n }[/math]. Let [math]\displaystyle{ A(G) }[/math] denote the adjacency matrix of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ D(G) = diag(deg_{1}, \ldots, deg_{n}) }[/math] be the diagonal matrix of vertex degrees. The Laplacian matrix of [math]\displaystyle{ G }[/math] is then [math]\displaystyle{ L(G) = D(G) - A(G) }[/math]. The eigenvalues of [math]\displaystyle{ L(G) }[/math], denoted by [math]\displaystyle{ \mu_{1}(G), \mu_{2}(G), \ldots, \mu_{n}(G) }[/math], labeled so that [math]\displaystyle{ \mu_{1}(G) \geq \mu_{2}(G), \ldots, \mu_{n}(G) }[/math], are called the Laplacian eigenvalues of [math]\displaystyle{ G }[/math]. These eigenvalues form the Laplacian spectrum of [math]\displaystyle{ G }[/math]. Because [math]\displaystyle{ L(G) }[/math] is a positive semidefinite symmetric matrix, the Laplacian eigenvalues are non-negative real-valued numbers.

For a weighted graph [math]\displaystyle{ G }[/math] on vertices labelled [math]\displaystyle{ 1, \ldots, n }[/math], the Laplacian matrix of [math]\displaystyle{ G }[/math] is the [math]\displaystyle{ n \times n }[/math] matrix [math]\displaystyle{ L }[/math] with

[math]\displaystyle{ L_{ij} = \left\{\begin{array}{l} -\theta,\mbox{ if }i\neq j\mbox{ and }(i,j)\mbox{ is an edge of }G\mbox{ with weight }\theta, \\ 0, \mbox{ if }(i,j)\mbox{ and }(i,j)\mbox{ is not an edge of }G, \\ \mbox{the sum of weights of edges incident with }i,\mbox{ if }i=j\end{array}\right. }[/math]

It is well-known that if [math]\displaystyle{ G }[/math] is connected, then the nullity of [math]\displaystyle{ L }[/math] is 1, and the null space of [math]\displaystyle{ L }[/math] is spanned by the all ones vector, [math]\displaystyle{ 1_{n} }[/math]. The second smallest eigenvalue of [math]\displaystyle{ L }[/math] is known as the algebraic connectivity of [math]\displaystyle{ G }[/math].