Графы де Брюина — различия между версиями
Anverk (обсуждение | вклад) (Новая страница: «== Основные определения == {{Определение |id = de_bruijn_graph |definition = '''Графом де Брюина''' (англ. ''De B...») |
(нет различий)
|
Версия 18:40, 30 ноября 2017
Основные определения
Определение: |
Графом де Брюина (англ. De Bruijn graph) с параметром | для -буквенного алфавита называется ориентированный граф , где множество всех строк длины в заданном алфавите, и слово длины в заданном алфавите такое, что
Основные свойства
- полный граф. Действительно, для любых (необязательно различных) вершин , где слова (символы), соответствующие вершинам . И тогда очевидно, что существует ребро