Laplacian matrix

In the mathematical field of graph theory, the Laplacian matrix, sometimes called admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. The Laplacian matrix can be used to find many useful properties of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the second smallest eigenvalue of its Laplacian by Cheeger's inequality.

Given a simple graph G with n vertices, its Laplacian matrix ${\displaystyle L_{n\times n}}$ is defined as:

where D is the degree matrix and A is the adjacency matrix of the graph. Since ${\displaystyle G}$ is a simple graph, ${\displaystyle A}$ only contains 1s or 0s and its diagonal elements are all 0s. In the case of directed graphs, either the indegree or outdegree might be used, depending on the application. The elements of ${\displaystyle L}$ are given by

...
Wikipedia