de Bruijn digraph

From Wikipedia, the free encyclopedia


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 a_1a_2\dots a_n connects the vertex a_1a_2\dots a_{n-1} to the vertex a_2a_3\dots a_n.

For example, B(2,4) could be drawn as:

Image:De Bruijin digraph.png

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.