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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Послідовність де Брейна — циклічний порядок , елементи якого належать заданій скінченній множині (зазвичай розглядають множину ), такий, що всі його підпослідовності [1] заданої довжини різні.

Часто розглядаються періодичні послідовності з періодом , що містять різних підпослідовностей , — тобто такі періодичні послідовності, в яких будь-який відрізок довжини є послідовністю де Брейна з тими самими параметрами і .

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

Властивості

[ред. | ред. код]

Очевидно, що довжина (період) такого циклу не може перевищувати  — числа всіх різних векторів довжини з елементами з ; нескладно довести, що ця оцінка досягається. Цикли цієї максимально можливої довжини зазвичай називають циклами де Брейна (втім, іноді цей термін застосовують і до циклів меншої довжини).

При існують такі цикли де Брейна з довжиною, на одиницю меншою максимуму, які виражаються лінійними рекурентними співвідношеннями порядку  : так, при співвідношення породжує послідовності з періодом 7, наприклад 0010111001011100 … (цикл де Брейна 0010111). На основі таких послідовностей побудовано, зокрема, циклічний надлишковий код CRC32 (EDB88320).

Приклади

[ред. | ред. код]

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

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

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

[ред. | ред. код]

Кількість циклів де Брейна з параметрами і є (окремий випадок теореми де Брейна — BEST-теорема[en], названа за прізвищами де Брейна, Тетяни Еренфест, Седріка Сміта і Вільяма Татта).

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

[ред. | ред. код]

Існує зручна інтерпретація послідовностей і циклів де Брейна, заснована на так званому графі де Брейна — орієнтованому графі з вершинами, що відповідають різним наборам довжини з елементами з , у якому з вершини у вершину ребро веде в тому і тільки тому випадку, коли (); при цьому самому ребру можна зіставити набір довжини  : . Для такого графу ейлерові шляхи (ейлерові цикли), що не проходять двічі через одне й те саме ребро, відповідають послідовності (циклу) де Брейна з параметрами і , а гамільтонові шляхи (гамільтонові цикли), що не проходять двічі через одну і ту ж вершину, — послідовності (циклу) де Брейна з параметрами і .

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

Примітки

[ред. | ред. код]
  1. Якщо , то в циклічному порядку вибирається елемент з індексом
  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.