NumberOfSpanningTrees - Maple Help

Online Help

All Products    Maple    MapleSim


GraphTheory

  

NumberOfSpanningTrees

  

number of spanning trees of graph

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

NumberOfSpanningTrees(G)

Parameters

G

-

graph

Description

• 

NumberOfSpanningTrees(G) returns the number of labeled spanning trees of the graph G.

• 

The strategy is to evaluate the determinant of a certain matrix related to the graph. (See Introduction to Graph Theory, by Douglas B. West)

Examples

withGraphTheory:

K3CompleteGraph3

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

(1)

NumberOfSpanningTreesK3

3

(2)

K4CompleteGraph4

K4Graph 2: an undirected unweighted graph with 4 vertices and 6 edge(s)

(3)

NumberOfSpanningTreesK4

16

(4)

See Also

IsTree

SpanningTree