GraphTheory
LaplacianMatrix
compute Laplacian or Kirchhoff matrix
Calling Sequence
Parameters
Options
Description
Definition
Examples
Compatibility
LaplacianMatrix(G, options)
G
-
graph
options
normalized, storage, datatype, or order
The options argument can contain one or more of the options shown below.
normalized=truefalse
If the option normalized is specified, then Laplacian matrix L is normalized so that Li,i=1 and Li,j=−1didj if there is an edge from vertex i to vertex j and 0 otherwise.
datatype, order, and storage
The Matrix options datatype, order, and storage may be specified. The default values of these options are anything, C_order, and rectangular respectively. For information on the use of these options, see the Matrix help page.
The LaplacianMatrix command returns the Laplacian matrix L of a simple undirected graph G. The Laplacian matrix is sometimes called the Kirchhoff matrix. It is defined as follows:
If G has n vertices and di is the degree of the ith vertex in G, then L is an n by n symmetric matrix where Li,i=di and Li,j is -1 if there is an edge from vertex i to vertex j and 0 otherwise.
withGraphTheory:
G≔PathGraph4
G≔Graph 1: an undirected graph with 4 vertices and 3 edge(s)
AdjacencyMatrixG
0100101001010010
LaplacianMatrixG
1−100−12−100−12−100−11
LaplacianMatrixG,normalized
1−2200−221−1200−121−2200−221
LaplacianMatrixG,normalized,datatype=float8
1.−0.7071067811865470.0.−0.7071067811865471.−0.5000000000000000.0.−0.5000000000000001.−0.7071067811865470.0.−0.7071067811865471.
Kirchhoff's theorem states that the number of spanning trees of a graph G is the product of the nonzero eigenvalues of the Laplacian matrix of G divided by n the number of vertices of G. Let us verify that the triangle graph K3 has three spanning trees.
K3≔CompleteGraph3
K3≔Graph 2: an undirected graph with 3 vertices and 3 edge(s)
EdgesK3
1,2,1,3,2,3
n≔numelemsVerticesK3
n≔3
L≔LaplacianMatrixK3
L≔2−1−1−12−1−1−12
E≔LinearAlgebra:-EigenvaluesL
E≔033
E2E3n
3
The GraphTheory[LaplacianMatrix] command was introduced in Maple 17.
For more information on Maple 17 changes, see Updates in Maple 17.
See Also
AdjacencyMatrix
Download Help Document