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

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

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

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

Властивості

Очевидно, що довжина (період) такого циклу не може перевищувати $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$ .

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

Примітки

Якщо $j>t$ , то в циклічному порядку вибирається елемент з індексом $j{\bmod {t}}$
de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764.
Flye Sainte-Marie C. Question 48 // L'intermédiaire math. — 1894. — v. 1. — pp. 107—110.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Якщо $j>t$ , то в циклічному порядку вибирається елемент з індексом $j{\bmod {t}}$

[2] de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764.

[3] Flye Sainte-Marie C. Question 48 // L'intermédiaire math. — 1894. — v. 1. — pp. 107—110.