LaplacianMatrix - Maple Help

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:
 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 unweighted 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}\left[8\right]\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 unweighted 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\left[2\right]E\left[3\right]}{n}$
 ${3}$ (11)

Compatibility

 • The GraphTheory[LaplacianMatrix] command was introduced in Maple 17.