Послідовність де Брейна — циклічний порядок , елементи якого належать заданій скінченній множині (зазвичай розглядають множину ), такий, що всі його підпослідовності заданої довжини різні.
Часто розглядаються періодичні послідовності з періодом , що містять різних підпослідовностей , — тобто такі періодичні послідовності, в яких будь-який відрізок довжини є послідовністю де Брейна з тими самими параметрами і .
Цикли названо так на честь нідерландського математика Ніколаса де Брейна, який вивчав їх , хоча вони вивчалися й раніше.
Властивості
Очевидно, що довжина (період) такого циклу не може перевищувати — числа всіх різних векторів довжини
з елементами з
; нескладно довести, що ця оцінка досягається. Цикли цієї максимально можливої довжини зазвичай називають циклами де Брейна (втім, іноді цей термін застосовують і до циклів меншої довжини).
При існують такі цикли де Брейна з довжиною, на одиницю меншою максимуму, які виражаються лінійними рекурентними співвідношеннями порядку
: так, при
співвідношення
породжує послідовності з періодом 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
Кількість циклів де Брейна
Кількість циклів де Брейна з параметрами і
є
(окремий випадок теореми де Брейна — [en], названа за прізвищами де Брейна, Тетяни Еренфест, і Вільяма Татта).
Граф де Брейна
Існує зручна інтерпретація послідовностей і циклів де Брейна, заснована на так званому графі де Брейна — орієнтованому графі з вершинами, що відповідають
різним наборам довжини
з елементами з
, у якому з вершини
у вершину
ребро веде в тому і тільки тому випадку, коли
(
); при цьому самому ребру можна зіставити набір довжини
:
. Для такого графу ейлерові шляхи (ейлерові цикли), що не проходять двічі через одне й те саме ребро, відповідають послідовності (циклу) де Брейна з параметрами
і
, а гамільтонові шляхи (гамільтонові цикли), що не проходять двічі через одну і ту ж вершину, — послідовності (циклу) де Брейна з параметрами
і
.
Граф де Брейна широко застосовується в біоінформатиці в задачах складання геному.
Примітки
- Якщо
, то в циклічному порядку вибирається елемент з індексом
- 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Poslidovnist de Brejna ciklichnij poryadok a1 at displaystyle a 1 ldots a t elementi yakogo nalezhat zadanij skinchennij mnozhini zazvichaj rozglyadayut mnozhinu 0 1 k 1 displaystyle 0 1 ldots k 1 takij sho vsi jogo pidposlidovnosti ai 1 ai n displaystyle a i 1 ldots a i n zadanoyi dovzhini n displaystyle n rizni Chasto rozglyadayutsya periodichni poslidovnosti z periodom T displaystyle T sho mistyat T displaystyle T riznih pidposlidovnostej ai 1 ai n displaystyle a i 1 ldots a i n tobto taki periodichni poslidovnosti v yakih bud yakij vidrizok dovzhini T n 1 displaystyle T n 1 ye poslidovnistyu de Brejna z timi samimi parametrami n displaystyle n i k displaystyle k Cikli nazvano tak na chest niderlandskogo matematika Nikolasa de Brejna yakij vivchav yih hocha voni vivchalisya j ranishe VlastivostiOchevidno sho dovzhina period takogo ciklu ne mozhe perevishuvati kn displaystyle k n chisla vsih riznih vektoriv dovzhini n displaystyle n z elementami z 0 1 k 1 displaystyle 0 1 ldots k 1 neskladno dovesti sho cya ocinka dosyagayetsya Cikli ciyeyi maksimalno mozhlivoyi dovzhini zazvichaj nazivayut ciklami de Brejna vtim inodi cej termin zastosovuyut i do cikliv menshoyi dovzhini Pri k 2 displaystyle k 2 isnuyut taki cikli de Brejna z dovzhinoyu na odinicyu menshoyu maksimumu yaki virazhayutsya linijnimi rekurentnimi spivvidnoshennyami poryadku n displaystyle n tak pri n 3 displaystyle n 3 spivvidnoshennya xn xn 2 xn 3 mod2 displaystyle x n x n 2 x n 3 pmod 2 porodzhuye poslidovnosti z periodom 7 napriklad 0010111001011100 cikl de Brejna 0010111 Na osnovi takih poslidovnostej pobudovano zokrema ciklichnij nadlishkovij kod CRC32 EDB88320 PrikladiPrikladi cikliv de Brejna dlya k 2 displaystyle k 2 z periodom 2 4 8 16 01 mistit pidposlidovnosti 0 i 1 0011 mistit pidposlidovnosti 00 01 11 10 00010111 000 001 010 101 011 111 110 100 0000100110101111Kilkist cikliv de BrejnaKilkist cikliv de Brejna z parametrami n displaystyle n i k displaystyle k ye k k n 1 kn displaystyle k k n 1 k n okremij vipadok teoremi de Brejna en nazvana za prizvishami de Brejna Tetyani Erenfest i Vilyama Tatta Graf de BrejnaIsnuye zruchna interpretaciya poslidovnostej i cikliv de Brejna zasnovana na tak zvanomu grafi de Brejna oriyentovanomu grafi z kn displaystyle k n vershinami sho vidpovidayut kn displaystyle k n riznim naboram dovzhini n displaystyle n z elementami z 0 1 k 1 displaystyle 0 1 ldots k 1 u yakomu z vershini x1 xn displaystyle x 1 ldots x n u vershinu y1 yn displaystyle y 1 ldots y n rebro vede v tomu i tilki tomu vipadku koli xi yi 1 displaystyle x i y i 1 i 2 n displaystyle i 2 ldots n pri comu samomu rebru mozhna zistaviti nabir dovzhini n 1 displaystyle n 1 x1 xn yn x1 y1 yn displaystyle x 1 ldots x n y n x 1 y 1 ldots y n Dlya takogo grafu ejlerovi shlyahi ejlerovi cikli sho ne prohodyat dvichi cherez odne j te same rebro vidpovidayut poslidovnosti ciklu de Brejna z parametrami n 1 displaystyle n 1 i k displaystyle k a gamiltonovi shlyahi gamiltonovi cikli sho ne prohodyat dvichi cherez odnu i tu zh vershinu poslidovnosti ciklu de Brejna z parametrami n displaystyle n i k displaystyle k Graf de Brejna shiroko zastosovuyetsya v bioinformatici v zadachah skladannya genomu PrimitkiYaksho j gt t displaystyle j gt t to v ciklichnomu poryadku vibirayetsya element z indeksom jmodt displaystyle 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 intermediaire math 1894 v 1 pp 107 110