De Bruijn graph

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

The De Bruijn graph [math]\displaystyle{ \,{\mathcal D}(n) }[/math] is a directed graph of order [math]\displaystyle{ \,2^{n} }[/math] 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 graph of [math]\displaystyle{ \,d }[/math] symbols is a directed graph [math]\displaystyle{ \,B(d,n) }[/math] representing overlaps between [math]\displaystyle{ \,n }[/math]-sequences of a [math]\displaystyle{ \,d }[/math] symbols. [math]\displaystyle{ \,B(d,n) }[/math] has [math]\displaystyle{ \,d^{n} }[/math] vertices from [math]\displaystyle{ \,Z_{d}^{n}=\big\{(1,1,\dots,1,1)(1,1,\dots,1,2),\dots,(1,1,\dots,1,d) (1,1,\dots,2,1),\dots,(d,d,\dots,d,d)\big\} }[/math]. The arcs of [math]\displaystyle{ \,B(d,n) }[/math] connect each vertex [math]\displaystyle{ \,(v_{1},v_{2},\dots,v_{n-1},v_{n}) }[/math] to a vertex [math]\displaystyle{ \,(w_{1},w_{2},\dots,w_{n-1},w_{n}) }[/math] such that [math]\displaystyle{ \,v_{2}=w_{1},v_{3}=w_{2},\dots,v_{n}=w_{n-1} }[/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].

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.