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=−1di⁢dj 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.
with⁡GraphTheory:
G ≔ PathGraph⁡4
G≔Graph 1: an undirected graph with 4 vertices and 3 edge(s)
AdjacencyMatrix⁡G
0100101001010010
LaplacianMatrix⁡G
1−100−12−100−12−100−11
LaplacianMatrix⁡G,normalized
1−2200−221−1200−121−2200−221
LaplacianMatrix⁡G,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 ≔ CompleteGraph⁡3
K3≔Graph 2: an undirected graph with 3 vertices and 3 edge(s)
Edges⁡K3
1,2,1,3,2,3
n ≔ numelems⁡Vertices⁡K3
n≔3
L ≔ LaplacianMatrix⁡K3
L≔2−1−1−12−1−1−12
E ≔ LinearAlgebra:-Eigenvalues⁡L
E≔033
E2⁢E3n
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
What kind of issue would you like to report? (Optional)