- Последовательность де Брёйна
-
Последовательность де Брёйна[1] — последовательность
, элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество
), и все подпоследовательности
заданной длины
, различны.
Часто рассматриваются периодические последовательности с периодом
, содержащие
различных подпоследовательностей
— то есть такие периодические последовательности, в которых любой отрезок длины
является последовательностью де Брёйна с теми же параметрами
и
.
Циклы де Брёйна названы по имени голландского математика Николаса де Брёйна, который рассматривал их в 1946 году[2], хотя они изучались и ранее[3].
Содержание
Свойства
Очевидно, что длина (период) такого цикла не может превосходить числа
всех различных векторов длины
с элементами из
; несложно доказать, что эта оценка достигается. Циклы этой максимально возможной длины обычно называют циклами де Брёйна (впрочем, иногда этот термин применяют и к циклам меньшей длины).
При
существуют такие циклы де Брёйна с длиной, на единицу меньшей максимума, которые выражаются линейными рекуррентными соотношениями порядка
: так, при
соотношение
порождает последовательности с периодом 7, например 0010111001011100… (цикл де Брёйна 0010111). На основе таких последовательностей построен, в частности, циклический избыточный код CRC32 (EDB88320).
Примеры
Примеры циклов де Брёйна для
с периодом 2, 4, 8, 16:
- 01 (содержит подпоследовательности 0 и 1)
- 0011 (содержит подпоследовательности 00, 01, 11, 10)
- 00010111 (000, 001, 010, 101, 011, 111, 110, 100)
- 0000100110101111
Количество циклов де Брёйна
Количество циклов де Брёйна с параметрами
и
есть
(частный случай теоремы де Брёйна — Эренфест (англ.) — Смита (англ.) — Тутте (англ.), BEST-теорема (англ.)).
Граф де Брёйна
Существует удобная интерпретация последовательностей и циклов де Брёйна, основанная на так называемом графе де Брёйна — ориентированном графе с
вершинами, соответствующими
различных наборов длины
с элементами из
, в котором из вершины
в вершину
ребро ведёт в том и только том случае, когда
(
); при этом самому ребру можно сопоставить набор длины
:
. Для такого графа не проходящие дважды через одно и то же ребро эйлеровы пути (эйлеровы циклы) соответствуют последовательности (циклу) де Брёйна с параметрами
и
, а не проходящие дважды через одну и ту же вершину гамильтоновы пути (гамильтоновы циклы) — последовательности (циклу) де Брёйна с параметрами
и
.
Граф де Брёйна широко применяется в биоинформатике в задачах сборки генома.
Примечания
Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.Категории:- Комбинаторика
- Ряды и последовательности
Wikimedia Foundation. 2010.