7
правок
Laplacian matrix: различия между версиями
Материал из WikiGrapp
м
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''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…») |
ALEXM (обсуждение | вклад) мНет описания правки |
||
| Строка 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>. | ||
