14-10-2023
Последовательность де Брёйна[1] — последовательность , элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество ), и все подпоследовательности заданной длины , различны.
Часто рассматриваются периодические последовательности с периодом , содержащие различных подпоследовательностей — то есть такие периодические последовательности, в которых любой отрезок длины является последовательностью де Брёйна с теми же параметрами и .
Циклы де Брёйна названы по имени голландского математика Николаса де Брёйна, который рассматривал их в 1946 году[2], хотя они изучались и ранее[3].
Содержание |
Очевидно, что длина (период) такого цикла не может превосходить числа всех различных векторов длины с элементами из ; несложно доказать, что эта оценка достигается. Циклы этой максимально возможной длины обычно называют циклами де Брёйна (впрочем, иногда этот термин применяют и к циклам меньшей длины).
При существуют такие циклы де Брёйна с длиной, на единицу меньшей максимума, которые выражаются линейными рекуррентными соотношениями порядка : так, при соотношение порождает последовательности с периодом 7, например 0010111001011100… (цикл де Брёйна 0010111). На основе таких последовательностей построен, в частности, циклический избыточный код CRC32 (EDB88320).
Примеры циклов де Брёйна для с периодом 2, 4, 8, 16:
Количество циклов де Брёйна с параметрами и есть (частный случай теоремы де Брёйна — Эренфест (англ.) — Смита (англ.) — Тутте (англ.), BEST-теорема (англ.)).
Существует удобная интерпретация последовательностей и циклов де Брёйна, основанная на так называемом графе де Брёйна — ориентированном графе с вершинами, соответствующими различных наборов длины с элементами из , в котором из вершины в вершину ребро ведёт в том и только том случае, когда (); при этом самому ребру можно сопоставить набор длины : . Для такого графа не проходящие дважды через одно и то же ребро эйлеровы пути (эйлеровы циклы) соответствуют последовательности (циклу) де Брёйна с параметрами и , а не проходящие дважды через одну и ту же вершину гамильтоновы пути (гамильтоновы циклы) — последовательности (циклу) де Брёйна с параметрами и .
Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Цикл де Брейна.