De Bruijn graph

De Bruijn graph --- граф де Брёйна.

The De Bruijn graph [math]\displaystyle{ {\mathcal D}(n) }[/math] of order [math]\displaystyle{ n }[/math] is a directed graph whose vertices comprise the set [math]\displaystyle{ Z_{2}^{n} }[/math]. The arcs of [math]\displaystyle{ {\mathcal D}(n) }[/math] connect each vertex [math]\displaystyle{ \alpha x }[/math], where [math]\displaystyle{ \alpha \in Z_{2} }[/math] and [math]\displaystyle{ x \in Z_{2}^{n-1} }[/math], to vertices [math]\displaystyle{ x0 }[/math] and [math]\displaystyle{ x1 }[/math].

The De Bruijn undirected graph, denoted [math]\displaystyle{ UB(d,n) }[/math], is obtained from [math]\displaystyle{ B(d,n) }[/math] by deleting the orientation of all directed edges and omitting multiple edges and loops. Clearly, [math]\displaystyle{ UB(d,1) }[/math] is a complete graph of order [math]\displaystyle{ d }[/math].