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
What kind of issue would you like to report? (Optional)