compute Laplacian or Kirchhoff matrix
normalized, storage, datatype, or order
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.
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.
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.
G ≔ PathGraph⁡4
G≔Graph 1: an undirected unweighted graph with 4 vertices and 3 edge(s)
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 unweighted graph with 3 vertices and 3 edge(s)
n ≔ numelems⁡Vertices⁡K3
L ≔ LaplacianMatrix⁡K3
E ≔ LinearAlgebra:-Eigenvalues⁡L
The GraphTheory[LaplacianMatrix] command was introduced in Maple 17.
For more information on Maple 17 changes, see Updates in Maple 17.
Download Help Document
What kind of issue would you like to report? (Optional)