De Bruijn graph: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''De Bruijn graph''' — [[граф де Брёйна]].  
'''De Bruijn graph''' — ''[[граф де Брёйна]]''.  


The '''De Bruijn graph''' <math>{\mathcal D}(n)</math> is a directed graph of order <math>\,2^{n}</math>  whose
The '''De Bruijn graph''' <math>\,{\mathcal D}(n)</math> is a [[directed graph]] of order <math>\,2^{n}</math>  whose [[vertex|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 Z_{2}^{n-1}</math>, to vertices <math>\,x0</math> and <math>\,x1</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
Z_{2}^{n-1}</math>, to vertices <math>\,x0</math> and <math>\,x1</math>.


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>.
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 [[arc|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>.


The '''De Bruijn undirected graph''', denoted <math>\,UB(d,n)</math>, is obtained from
The '''De Bruijn [[undirected graph]]''', denoted <math>\,UB(d,n)</math>, is obtained from <math>\,B(d,n)</math> by deleting the orientation of all [[directed edge|directed edges]] and omitting multiple [[edge|edges]] and [[loop|loops]]. Clearly, <math>\,UB(d,1)</math> is a complete
<math>\,B(d,n)</math> by deleting the orientation of all directed edges and
[[graph, undirected graph, nonoriented graph|graph]] of order <math>\,d</math>.
omitting multiple edges and loops. Clearly, <math>\,UB(d,1)</math> is a complete
 
graph of order <math>\,d</math>.
==Литература==
*Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.
 
 
[[Категория:Основные термины]]

Навигация