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

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

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

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

Властивості

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

При $k=2$ існують такі цикли де Брейна з довжиною, на одиницю меншою максимуму, які виражаються лінійними рекурентними співвідношеннями порядку $n$ : так, при $n=3$ співвідношення $x_n=x_{n-2}+x_{n-3}(\mathrm{mod}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$ (окремий випадок теореми де Брейна — Шаблон:Iw, названа за прізвищами де Брейна, Тетяни Еренфест, Седріка Сміта і Вільяма Татта).

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

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

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