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.

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.

$\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(s)}$

$\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]$

$\mathrm{LaplacianMatrix}\left(G\right)$

$\left[\begin{array}{cccc}1& \mathrm{-1}& 0& 0\\ \mathrm{-1}& 2& \mathrm{-1}& 0\\ 0& \mathrm{-1}& 2& \mathrm{-1}\\ 0& 0& \mathrm{-1}& 1\end{array}\right]$

$\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]$

$\mathrm{LaplacianMatrix}\left(G\,\mathrm{normalized}\,\mathrm{datatype}\={\mathrm{float}}_8\right)$

$\left[\begin{array}{cccc}1.& \mathrm{-0.707106781186547}& 0.& 0.\\ \mathrm{-0.707106781186547}& 1.& \mathrm{-0.500000000000000}& 0.\\ 0.& \mathrm{-0.500000000000000}& 1.& \mathrm{-0.707106781186547}\\ 0.& 0.& \mathrm{-0.707106781186547}& 1.\end{array}\right]$

$\mathrm{K3}≔\mathrm{CompleteGraph}\left(3\right)$

$\mathrm{K3}≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 3\; vertices\; and\; 3\; edge(s)}$

$\mathrm{Edges}\left(\mathrm{K3}\right)$

$\left\{\left\{1\,2\right\}\,\left\{1\,3\right\}\,\left\{2\,3\right\}\right\}$

$n≔\mathrm{numelems}\left(\mathrm{Vertices}\left(\mathrm{K3}\right)\right)$

$n≔3$

$L≔\mathrm{LaplacianMatrix}\left(\mathrm{K3}\right)$

$L≔\left[\begin{array}{ccc}2& \mathrm{-1}& \mathrm{-1}\\ \mathrm{-1}& 2& \mathrm{-1}\\ \mathrm{-1}& \mathrm{-1}& 2\end{array}\right]$

$E≔\mathrm{LinearAlgebra}:-\mathrm{Eigenvalues}\left(L\right)$

$E≔\left[\begin{array}{c}0\\ 3\\ 3\end{array}\right]$

$\frac{E_2{E}_3}{n}$

$3$

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

For more information on Maple 17 changes, see Updates in Maple 17.