Tag Info

The Laplacian matrix is the representation of a graph in matrix form.

Consider a simple graph $$G$$. Given it's degree matrix $$D$$, and adjacency matrix $$A$$, the Laplacian is defined as

$$L = D - A$$

With all matrices having size $$|G| \times |G|$$

The degree matrix $$D$$ consists only of entries in the diagonal, with $$D_{i,i}$$ representing the degree of node $$i$$.
The adjacency has entries $$A_{i,j} = 1$$ when there is an edge in $$G$$ from $$i$$ to $$j$$. These entries could also be used to represent edge weight in the case of a weighted graph, or the number of edges in the case of a multigraph. If the graph is undirected, the matrix will be symmetric.

The eigenvalues and eigenvectors of the Laplacian provide a rich amount of information about the properties of a graph, this is the field of Spectral Graph Theory.
In particular, the number of connected components in the graph is equal to the multiplicity of the 0 eigenvalue. The second smallest eigenvalue (also called Fiedler Value) is useful for graph partitioning and linear arrangement problems.