DeBruijnGraph - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


GraphTheory[SpecialGraphs]

  

DeBruijnGraph

  

construct De Bruijn graph

 

Calling Sequence

Parameters

Description

Examples

Compatibility

Calling Sequence

DeBruijnGraph(m,n)

DeBruijnGraph(s,n)

Parameters

m

-

positive integer

n

-

positive integer

s

-

string of distinct characters

Description

• 

DeBruijnGraph(m,n) returns the De Bruijn graph, a directed graph whose vertices may be seen as sequences of symbols of length n chosen from some alphabet of size m and whose edges indicate those sequences which may overlap.

• 

The graph has  vertices, each of which corresponds to a sequence of the  symbols of length .

• 

DeBruijnGraph(s,n) returns a De Bruijn graph equivalent to DeBruijnGraph(length(s),n) but whose vertices are strings of length n composed from the characters in s. There is a directed edge from string t1 to a string t2 if there exists a string v of length n-1 and characters u,w in s such that t1=cat(u,v) and t2=cat(v,w).

• 

The graph is named for Nicolaas Govert de Bruijn.

Examples

(1)

(2)

(3)

(4)

(5)

Compatibility

• 

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

• 

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

• 

The GraphTheory[SpecialGraphs][DeBruijnGraph] command was updated in Maple 2023.

• 

The s parameter was introduced in Maple 2023.

• 

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

See Also

Iterator[DeBruijn]

SpecialGraphs

 


Download Help Document