Графы де Брюина

Материал из Викиконспекты
Версия от 18:40, 30 ноября 2017; Anverk (обсуждение | вклад) (Новая страница: «== Основные определения == {{Определение |id = de_bruijn_graph |definition = '''Графом де Брюина''' (англ. ''De B...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Основные определения

Определение:
Графом де Брюина (англ. De Bruijn graph) с параметром [math]l[/math] для [math]n[/math]-буквенного алфавита называется ориентированный граф [math]G(V, E)[/math], где [math] V - [/math] множество всех строк длины [math]l[/math] в заданном алфавите, и [math]e = (u, v) \in E \Leftrightarrow \exists [/math] слово [math]L[/math] длины [math]l+1[/math] в заданном алфавите такое, что [math] u = prefix(L) \wedge v = suffix(L) [/math]


Основные свойства

  • [math] |V| = n^l [/math]
  • [math] l = 1 \Leftrightarrow G - [/math] полный граф. Действительно, для любых (необязательно различных) вершин [math] u, v \ \exists L = \alpha \beta [/math], где [math] \alpha, \beta - [/math] слова (символы), соответствующие вершинам [math] u, v [/math]. И тогда очевидно, что существует ребро [math] e = (u, v)\ \forall u, v \in V [/math]