construct De Bruijn graph
string of distinct characters
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 mn vertices, each of which corresponds to a sequence of the m symbols of length n.
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.
G32 ≔ DeBruijnGraph⁡3,2
G32≔Graph 1: a directed graph with 9 vertices, 24 arc(s), and 3 self-loop(s)
G53 ≔ DeBruijnGraph⁡5,3
G53≔Graph 2: a directed graph with 125 vertices, 620 arc(s), and 5 self-loop(s)
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.
Download Help Document