# De Bruijn graph

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

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$.