Laplacian matrix: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''Laplacian matrix''' --- лапласиан. Let <math>G</math> be a simple graph on <math>n</math> vertices. Let <math>deg_{i}</math> denote the degree of a ver…»)
 
мНет описания правки
 
Строка 13: Строка 13:
For a weighted graph <math>G</math> on vertices labelled <math>1, \ldots, n</math>, the '''Laplacian matrix''' of <math>G</math> is the <math>n \times n</math> matrix <math>L</math> with
For a weighted graph <math>G</math> on vertices labelled <math>1, \ldots, n</math>, the '''Laplacian matrix''' of <math>G</math> is the <math>n \times n</math> matrix <math>L</math> with


<math>L_{ij} = \left\{\begin{array}{l} -\theta,\mbox{ if }i\neq j\mbox{
<math>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, \\
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, \\
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
\mbox{the sum of weights of edges incident with }i,\mbox{ if }i=j\end{array}\right.</math>
}i=j\end{array}\right.</math>


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

Текущая версия от 14:58, 24 сентября 2018

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].