GraphTheory[SpecialGraphs] - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory[SpecialGraphs]

  

DeBruijnGraph

  

construct De Bruijn graph

 

Calling Sequence

Parameters

Description

Examples

Compatibility

Calling Sequence

DeBruijnGraph(m,n)

Parameters

m

-

positive integer

n

-

positive integer

Description

• 

The DeBruijnGraph() command returns the De Bruijn graph, a directed graph whose vertices are sequences of symbols of length n chosen from some alphabet of size m whose edges indicate the sequences which may overlap.

• 

The graph has mn vertices, each of which corresponds to a sequence of the m symbols of length n.  It is named for Nicolaas Govert de Bruijn.

Examples

withGraphTheory:

withSpecialGraphs:

G32DeBruijnGraph3,2

G32Graph 1: a directed unweighted graph with 9 vertices, 24 arc(s), and 3 self-loop(s)

(1)

DrawGraphG32

G53DeBruijnGraph5,3

`Graph 2: a directed unweighted graph with 125 vertices, 620 arc(s), and 5 self-loop(s)`

Graph 2: a directed unweighted graph with 125 vertices, 620 arc(s), and 5 self-loop(s)

(2)

NumberOfSelfLoopsG53

5

(3)

NumberOfEdgesG53

625

(4)

IsEulerianG53

true

(5)

Compatibility

• 

The GraphTheory[SpecialGraphs][DeBruijnGraph] command was introduced in Maple 2020.

• 

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

See Also

Iterator[DeBruijn]

SpecialGraphs