Послідовність де Брейна

Послідовність де Брейна — циклічний порядок $a_{1},\;\ldots ,\;a_{t}$, елементи якого належать заданій скінченній множині (зазвичай розглядають множину $\{0,\;1,\;\ldots ,\;k-1\}$), такий, що всі його підпослідовності $a_{i+1},\;\ldots ,\;a_{i+n}$ заданої довжини $n$ різні.

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

Цикли названо так на честь нідерландського математика Ніколаса де Брейна, який вивчав їх 1946 році, хоча вони вивчалися й раніше.

Властивості

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

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

Приклади

Приклади циклів де Брейна для $k=2$ з періодом 2, 4, 8, 16:

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

Кількість циклів де Брейна

Кількість циклів де Брейна з параметрами $n$ і $k$ є $k!^{k^{(n-1)}}/k^{n}$ (окремий випадок теореми де Брейна — BEST-теорема, названа за прізвищами де Брейна, Тетяни Еренфест, Седріка Сміта і Вільяма Татта).

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

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

Граф де Брейна широко застосовується в біоінформатиці в задачах складання геному.