GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/LaplacianMatrix

GraphTheory

  

LaplacianMatrix

  

compute Laplacian or Kirchhoff matrix

 

Calling Sequence

Parameters

Description

Examples

Compatibility

Calling Sequence

LaplacianMatrix(G, options)

Parameters

G

-

graph

options

-

normalized, storage, datatype, or order

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 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=1didj 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.

Examples

withGraphTheory:

GPathGraph4

GGraph 1: an undirected unweighted graph with 4 vertices and 3 edge(s)

(1)

AdjacencyMatrixG

0100101001010010

(2)

LaplacianMatrixG

1−100−12−100−12−100−11

(3)

LaplacianMatrixG,normalized

1220022112001212200221

(4)

LaplacianMatrixG,normalized,datatype=float8

1.−0.7071067811865470.0.−0.7071067811865471.−0.5000000000000000.0.−0.5000000000000001.−0.7071067811865470.0.−0.7071067811865471.

(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.

K3CompleteGraph3

K3Graph 2: an undirected unweighted graph with 3 vertices and 3 edge(s)

(6)

EdgesK3

1,2,1,3,2,3

(7)

nnumelemsVerticesK3

n3

(8)

LLaplacianMatrixK3

L2−1−1−12−1−1−12

(9)

ELinearAlgebra:-EigenvaluesL

E033

(10)

E2E3n

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

AdjacencyMatrix