LaplacianMatrix - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim

GraphTheory

 LaplacianMatrix
 compute Laplacian or Kirchhoff matrix

 Calling Sequence LaplacianMatrix(G, options)

Parameters

 G - graph options - normalized, storage, datatype, or order

Options

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 ${L}_{i,i}=1$ and ${L}_{i,j}=-\frac{1}{\sqrt{{d}_{i}{d}_{j}}}$ 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.

Description

 • 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:

Definition

 • If G has $n$ vertices and ${d}_{i}$ is the degree of the $i$th vertex in G, then L is an $n$ by $n$ symmetric matrix where ${L}_{i,i}={d}_{i}$ and ${L}_{i,j}$ is -1 if there is an edge from vertex $i$ to vertex $j$ and 0 otherwise.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{PathGraph}\left(4\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 4 vertices and 3 edge\left(s\right)}}$ (1)
 > $\mathrm{AdjacencyMatrix}\left(G\right)$
 $\left[\begin{array}{cccc}{0}& {1}& {0}& {0}\\ {1}& {0}& {1}& {0}\\ {0}& {1}& {0}& {1}\\ {0}& {0}& {1}& {0}\end{array}\right]$ (2)
 > $\mathrm{LaplacianMatrix}\left(G\right)$
 $\left[\begin{array}{cccc}{1}& {-1}& {0}& {0}\\ {-1}& {2}& {-1}& {0}\\ {0}& {-1}& {2}& {-1}\\ {0}& {0}& {-1}& {1}\end{array}\right]$ (3)
 > $\mathrm{LaplacianMatrix}\left(G,\mathrm{normalized}\right)$
 $\left[\begin{array}{cccc}{1}& {-}\frac{\sqrt{{2}}}{{2}}& {0}& {0}\\ {-}\frac{\sqrt{{2}}}{{2}}& {1}& {-}\frac{{1}}{{2}}& {0}\\ {0}& {-}\frac{{1}}{{2}}& {1}& {-}\frac{\sqrt{{2}}}{{2}}\\ {0}& {0}& {-}\frac{\sqrt{{2}}}{{2}}& {1}\end{array}\right]$ (4)
 > $\mathrm{LaplacianMatrix}\left(G,\mathrm{normalized},\mathrm{datatype}={\mathrm{float}}_{8}\right)$
 $\left[\begin{array}{cccc}{1.}& {-0.707106781186547}& {0.}& {0.}\\ {-0.707106781186547}& {1.}& {-0.500000000000000}& {0.}\\ {0.}& {-0.500000000000000}& {1.}& {-0.707106781186547}\\ {0.}& {0.}& {-0.707106781186547}& {1.}\end{array}\right]$ (5)

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.

 > $\mathrm{K3}≔\mathrm{CompleteGraph}\left(3\right)$
 ${\mathrm{K3}}{≔}{\mathrm{Graph 2: an undirected graph with 3 vertices and 3 edge\left(s\right)}}$ (6)
 > $\mathrm{Edges}\left(\mathrm{K3}\right)$
 $\left\{\left\{{1}{,}{2}\right\}{,}\left\{{1}{,}{3}\right\}{,}\left\{{2}{,}{3}\right\}\right\}$ (7)
 > $n≔\mathrm{numelems}\left(\mathrm{Vertices}\left(\mathrm{K3}\right)\right)$
 ${n}{≔}{3}$ (8)
 > $L≔\mathrm{LaplacianMatrix}\left(\mathrm{K3}\right)$
 ${L}{≔}\left[\begin{array}{ccc}{2}& {-1}& {-1}\\ {-1}& {2}& {-1}\\ {-1}& {-1}& {2}\end{array}\right]$ (9)
 > $E≔\mathrm{LinearAlgebra}:-\mathrm{Eigenvalues}\left(L\right)$
 ${E}{≔}\left[\begin{array}{c}{0}\\ {3}\\ {3}\end{array}\right]$ (10)
 > $\frac{{E}_{2}{E}_{3}}{n}$
 ${3}$ (11)

Compatibility

 • The GraphTheory[LaplacianMatrix] command was introduced in Maple 17.
 • For more information on Maple 17 changes, see Updates in Maple 17.

 See Also