De Bruijn digraph
From Wikipedia, the free encyclopedia
- The correct title of this article is de Bruijn digraph. The initial letter is shown capitalized due to technical restrictions.
The vertices of the de Bruijn digraph B(n,m) are all possible words of length m − 1 chosen from an alphabet of size n.
B(n,m) has nm edges consisting of each possible word of length m from an alphabet of size n. The edge 
connects the vertex 
to the vertex 
.
For example, B(2,4) could be drawn as:
Notice that an Euler cycle on B(n,m) represents a shortest sequence of characters from an alphabet of size n that includes every possible subsequence of m characters. For example, the sequence 000011110010101000 includes all 4-bit subsequences. Any de Bruijn digraph must have an Euler cycle, since each vertex has in degree and out degree of m.
This article incorporates material from De Bruijn digraph on PlanetMath, which is licensed under the GFDL.
