De Bruijn graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''De Bruijn graph''' --- граф де Брёйна. The '''De Bruijn graph''' <math>{\mathcal D}(n)</math> of order <math>n</math> is a directed graph whose ver…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''De Bruijn graph''' | '''De Bruijn graph''' — [[граф де Брёйна]]. | ||
The '''De Bruijn graph''' <math>{\mathcal D}(n)</math> of order <math>n</math> | The '''De Bruijn graph''' <math>{\mathcal D}(n)</math> is a directed graph of order <math>\,2^{n}</math> whose | ||
vertices comprise the set <math>Z_{2}^{n}</math>. The arcs of <math>{\mathcal D}(n)</math> | vertices comprise the set <math>Z_{2}^{n}</math>. The arcs of <math>{\mathcal D}(n)</math> | ||
connect each vertex <math>\alpha x</math>, where <math>\alpha \in Z_{2}</math> and <math>x \in | connect each vertex <math>\,\alpha x</math>, where <math>\alpha \in Z_{2}</math> and <math>x \in | ||
Z_{2}^{n-1}</math>, to vertices <math>x0</math> and <math>x1</math>. | Z_{2}^{n-1}</math>, to vertices <math>\,x0</math> and <math>\,x1</math>. | ||
The '''De Bruijn undirected graph''', denoted <math>UB(d,n)</math>, is obtained from | The '''De Bruijn graph''' of <math>\,d</math> symbols is a directed graph <math>\,B(d,n)</math> representing overlaps between <math>\,n</math>-sequences of a <math>\,d</math> symbols. <math>\,B(d,n)</math> has <math>\,d^{n}</math> vertices from <math>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>\,B(d,n)</math> connect each vertex <math>\,(v_{1},v_{2},\dots,v_{n-1},v_{n})</math> to a vertex <math>\,(w_{1},w_{2},\dots,w_{n-1},w_{n})</math> such that <math>\,v_{2}=w_{1},v_{3}=w_{2},\dots,v_{n}=w_{n-1}</math>. | ||
<math>B(d,n)</math> by deleting the orientation of all directed edges and | |||
omitting multiple edges and loops. Clearly, <math>UB(d,1)</math> is a complete | The '''De Bruijn undirected graph''', denoted <math>\,UB(d,n)</math>, is obtained from | ||
graph of order <math>d</math>. | <math>\,B(d,n)</math> by deleting the orientation of all directed edges and | ||
omitting multiple edges and loops. Clearly, <math>\,UB(d,1)</math> is a complete | |||
graph of order <math>\,d</math>. | |||
Текущая версия от 18:13, 22 марта 2011
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].