Combinatorics Spectral and algebraic graph theory Concept
Laplacian matrix
Summary
The Laplacian matrix of a finite graph is the degree matrix minus the adjacency matrix. It is symmetric and positive semidefinite, and its eigenvalues carry information about connectivity: the number of connected components is the multiplicity of the eigenvalue . Through Kirchhoff's matrix tree theorem it counts spanning trees, and its second smallest eigenvalue controls how well the graph is connected. It is the discrete analogue of the Laplace operator of analysis.
Where this leads
6 pages build on this one.
Further reading
About this page
| Tag | TN6M6DVZRP |
|---|---|
| URI | m2://TN6M6DVZRP |
| Kind | concept |
| Writing | W0 stub |
| MSC | 05C50 |
| Same as |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
Used by
- Effective resistance
- Discrete harmonic function
- Kirchhoff's matrix tree theorem
- Discrete Laplace operator
- Kigami's construction of Laplacians on post-critically finite fractals
- Incidence matrix