De Bruijn Digraph

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

n^{m}

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:

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

	CATEGORIES ABOUT DE BRUIJN DIGRAPH

	combinatorics

Information About