Laplacian matrix

From Wikipedia, the free encyclopedia

You have new messages (last change).

In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph.

[edit] Definition

The Laplacian of a graph G is defined as

L: = D − A

with D the degree matrix of G and A the adjacency matrix of G.

More explicitly, given a graph G with n vertices, the matrixL:=(l_{i,j})_{n \times n} satisfies

l_{i,j}:=\left\{ \begin{matrix} \deg(v_i) & \mbox{if}\ i = j \\ -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i\ \mbox{adjacent}\ v_j \\ 0 & \mbox{otherwise} \end{matrix} \right.

In the case of directed graphs, either the indegree or the outdegree might be used, depending on the application.

[edit] Properties

For a graph G and its admittance matrix L with eigenvalues \lambda_0 \le \lambda_1 \le \ldots \le \lambda_{n-1}:

L is always positive-semidefinite (\forall i, \lambda_i \ge 0).

The multiplicity of 0 as an eigenvalue of L is the number of connected components of G.

λ1 is called the algebraic connectivity.

The smallest non-trivial eigenvalue of L is called the spectral gap.

[edit] See also

Retrieved from "http://en.wikipedia.org../../../l/a/p/Laplacian_matrix.html"
In other languages