De Bruijn graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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

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