compute Laplacian or Kirchhoff matrix
normalized, storage, datatype, or order
The options argument can contain one or more of the options shown below.
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.
G ≔ PathGraph⁡4
G≔Graph 1: an undirected 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 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