WikiSort.ru - Не сортированное

Последовательность де Брёйна^[1] — последовательность ${\displaystyle a_{1},\;\ldots ,\;a_{t}}$ , элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество ${\displaystyle \{0,\;1,\;\ldots ,\;k-1\}}$ ), такая, что все её подпоследовательности ${\displaystyle a_{i+1},\;\ldots ,\;a_{i+n}}$ заданной длины ${\displaystyle n}$ различны.

Часто рассматриваются периодические последовательности с периодом ${\displaystyle T}$ , содержащие ${\displaystyle T}$ различных подпоследовательностей ${\displaystyle a_{i+1},\;\ldots ,\;a_{i+n}}$ , — то есть такие периодические последовательности, в которых любой отрезок длины ${\displaystyle T+n-1}$ является последовательностью де Брёйна с теми же параметрами ${\displaystyle n}$ и ${\displaystyle k}$ .

Циклы де Брёйна названы по имени голландского математика Николаса де Брёйна, который рассматривал их в 1946 году^[2], хотя они изучались и ранее^[3].

Свойства

Очевидно, что длина (период) такого цикла не может превосходить ${\displaystyle k^{n}}$ — числа́ всех различных векторов длины ${\displaystyle n}$ с элементами из ${\displaystyle \{0,\;1,\;\ldots ,\;k-1\}}$ ; несложно доказать, что эта оценка достигается. Циклы этой максимально возможной длины обычно называют циклами де Брёйна (впрочем, иногда этот термин применяют и к циклам меньшей длины).

При ${\displaystyle k=2}$ существуют такие циклы де Брёйна с длиной, на единицу меньшей максимума, которые выражаются линейными рекуррентными соотношениями порядка ${\displaystyle n}$ : так, при ${\displaystyle n=3}$ соотношение ${\displaystyle x_{n}=x_{n-2}+x_{n-3}{\pmod {2}}}$ порождает последовательности с периодом 7, например 0010111001011100… (цикл де Брёйна 0010111). На основе таких последовательностей построен, в частности, циклический избыточный код CRC32 (EDB88320).

Примеры

Примеры циклов де Брёйна для ${\displaystyle k=2}$ с периодом 2, 4, 8, 16:

• 01 (содержит подпоследовательности 0 и 1)
• 0011 (содержит подпоследовательности 00, 01, 11, 10)
• 00010111 (000, 001, 010, 101, 011, 111, 110, 100)
• 0000100110101111

Количество циклов де Брёйна

Количество циклов де Брёйна с параметрами ${\displaystyle n}$ и ${\displaystyle k}$ есть ${\displaystyle k!^{k^{(n-1)}}/k^{n}}$ (частный случай теоремы де Брёйна — BEST-теорема (англ.), названная по фамилиям де Брёйна, Татьяны Эренфест (англ.), Седрика Смита и Уильяма Татта (англ.)).

Граф де Брёйна

Существует удобная интерпретация последовательностей и циклов де Брёйна, основанная на так называемом графе де Брёйна — ориентированном графе с ${\displaystyle k^{n}}$ вершинами, соответствующими ${\displaystyle k^{n}}$ различных наборов длины ${\displaystyle n}$ с элементами из ${\displaystyle \{0,\;1,\;\ldots ,\;k-1\}}$ , в котором из вершины ${\displaystyle (x_{1},\;\ldots ,\;x_{n})}$ в вершину ${\displaystyle (y_{1},\;\ldots ,\;y_{n})}$ ребро ведёт в том и только том случае, когда ${\displaystyle x_{i}=y_{i-1}}$ (${\displaystyle i=2,\;\ldots ,\;n}$ ); при этом самому ребру можно сопоставить набор длины ${\displaystyle n+1}$ : ${\displaystyle (x_{1},\;\ldots ,\;x_{n},\;y_{n})=(x_{1},\;y_{1},\;\ldots ,\;y_{n})}$ . Для такого графа не проходящие дважды через одно и то же ребро эйлеровы пути (эйлеровы циклы) соответствуют последовательности (циклу) де Брёйна с параметрами ${\displaystyle n+1}$ и ${\displaystyle k}$ , а не проходящие дважды через одну и ту же вершину гамильтоновы пути (гамильтоновы циклы) — последовательности (циклу) де Брёйна с параметрами ${\displaystyle n}$ и ${\displaystyle k}$ .

Граф де Брёйна широко применяется в биоинформатике в задачах сборки генома.

Примечания

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.