Laplacian matrix

Laplacian matrix

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. The Laplacian matrix can be used to find many others properties of the graph, see spectral graph theory.

Definition

Given a graph "G" with "n" vertices (without loops or multiple edges), its Laplacian matrix L:=(ell_{i,j})_{n imes n} is defined as [Weisstein, Eric W. " [http://mathworld.wolfram.com/LaplacianMatrix.html Laplacian Matrix] ." From MathWorld—A Wolfram Web Resource.]

:ell_{i,j}:=egin{cases}deg(v_i) & mbox{if} i = j \-1 & mbox{if} i eq j mbox{and} v_i ext{ is adjacent to } v_j \0 & ext{otherwise}.end{cases}

That is, it is the difference of the degree matrix and the adjacency matrix of the graph.In the case of directed graphs, either the indegree or the outdegree might be used, depending on the application.

The normalized laplacian matrix is defined as [Weisstein, Eric W. " [http://mathworld.wolfram.com/LaplacianMatrix.html Laplacian Matrix] ." From MathWorld—A Wolfram Web Resource.]

:ell_{i,j}:=egin{cases}1 & mbox{if} i = j mbox{and} deg(v_i) eq 0\-frac{1}{sqrt{deg(v_i)deg(v_j) & mbox{if} i eq j mbox{and} v_i ext{ is adjacent to } v_j \0 & ext{otherwise}.end{cases}

Example

Here is a simple example of a labeled graph and its Laplacian matrix.

Properties

For a graph "G" and its Laplacian matrix "L" with eigenvalues lambda_0 le lambda_1 le cdots le lambda_{n-1}:

* "L" is always positive-semidefinite (forall i, lambda_i ge 0).
* The number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph.
* lambda_0 is always 0.
* lambda_1 is called the algebraic connectivity.
* The smallest non-trivial eigenvalue of "L" is called the spectral gap or Fiedler value.

Deformed Laplacian

The deformed Laplacian is commonly defined as

:Delta(s)=I-sA+s^2(D-I)

where "I" is the unit matrix, "A" is the adjacency matrix, and "D" is the degree matrix, and "s" is a (complex-valued) number. Note that normal Laplacian is just Delta(1).

As an operator

The Laplacian matrix can be generalized to the case of graphs with an infinite number of vertices and edges; this generalization is known as the discrete Laplace operator.

ee also

*Kirchhoff's theorem

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Matrix calculus — Topics in Calculus Fundamental theorem Limits of functions Continuity Mean value theorem Differential calculus  Derivative Change of variables Implicit differentiation Taylor s theorem Related rates …   Wikipedia

  • Degree matrix — In the mathematical field of graph theory the degree matrix is a diagonal matrix which contains information about the degree of each vertex. It is used together with the adjacency matrix to construct the Laplacian matrix of a graph. Definition… …   Wikipedia

  • Diagonal matrix — In linear algebra, a diagonal matrix is a matrix (usually a square matrix) in which the entries outside the main diagonal (↘) are all zero. The diagonal entries themselves may or may not be zero. Thus, the matrix D = (di,j) with n columns and n… …   Wikipedia

  • Hessian matrix — In mathematics, the Hessian matrix (or simply the Hessian) is the square matrix of second order partial derivatives of a function; that is, it describes the local curvature of a function of many variables. The Hessian matrix was developed in the… …   Wikipedia

  • M-matrix — In mathematics, especially linear algebra, an M matrix is a Z matrix with eigenvalues whose real parts are positive. M matrices are a subset of the class of P matrices, and also of the class of inverse positive matrices [Takao Fujimoto and… …   Wikipedia

  • Kirchhoff's theorem — In the mathematical field of graph theory Kirchhoff s theorem or Kirchhoff s matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph. It is a generalization of Cayley s formula which provides… …   Wikipedia

  • Nonlinear dimensionality reduction — High dimensional data, meaning data that requires more than two or three dimensions to represent, can be difficult to interpret. One approach to simplification is to assume that the data of interest lies on an embedded non linear manifold within… …   Wikipedia

  • Discrete Laplace operator — For the discrete equivalent of the Laplace transform, see Z transform. In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a… …   Wikipedia

  • Eigenvalues and eigenvectors — For more specific information regarding the eigenvalues and eigenvectors of matrices, see Eigendecomposition of a matrix. In this shear mapping the red arrow changes direction but the blue arrow does not. Therefore the blue arrow is an… …   Wikipedia

  • Laplace operator — This article is about the mathematical operator. For the Laplace probability distribution, see Laplace distribution. For graph theoretical notion, see Laplacian matrix. Del Squared redirects here. For other uses, see Del Squared (disambiguation) …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”