De Bryuyn grafigi - De Bruijn graph

Yilda grafik nazariyasi, an n- o'lchovli De Bryuyn grafigi ning m belgilar bir yo'naltirilgan grafik belgilar ketma-ketliklari orasidagi o'zaro to'qnashuvlarni aks ettiradi. Unda bor mⁿ tepaliklar mumkin bo'lgan barcha uzunliklardan iborat -n berilgan belgilarning ketma-ketliklari; bir xil belgi ketma-ketlikda bir necha marta paydo bo'lishi mumkin. Agar bizda to'plam mavjud bo'lsa m belgilar ${ displaystyle S: = {s_ {1}, nuqta, s_ {m} }}$ u holda tepaliklar to'plami:

${ displaystyle V = S ^ {n} = {(s_ {1}, dots, s_ {1}, s_ {1}), (s_ {1}, dots, s_ {1}, s_ {2 }), nuqta, (s_ {1}, nuqta, s_ {1}, s_ {m}), (s_ {1}, nuqta, s_ {2}, s_ {1}), nuqta, ( s_ {m}, nuqtalar, s_ {m}, s_ {m}) }.}$

Agar bironta tepalik sifatida uning barcha belgilarini bir joyga chap tomonga siljitish va shu tepaning oxiriga yangi belgi qo'shish orqali ifodalanishi mumkin bo'lsa, unda ikkinchisi oldingi tepaga yo'naltirilgan chekkaga ega. Shunday qilib, yoylarning to'plami (ya'ni yo'naltirilgan qirralarning)

${ displaystyle E = {((t_ {1}, t_ {2}, nuqtalar, t_ {n}), (t_ {2}, nuqtalar, t_ {n}, s_ {j})): t_ {i} in S, 1 leq i leq n, 1 leq j leq m }.}$

Garchi De Bruijn grafikalari nomi bilan nomlangan Nikolaas Gvert de Bryuyn, ular mustaqil ravishda ikkala De Bryuyn tomonidan kashf etilgan^[1] va I. J. Yaxshi.^[2] Bundan ancha oldin, Kamil Flay Seynt-Mari^[3] ularning xususiyatlaridan bevosita foydalanilgan.

Xususiyatlari

• Agar ${ displaystyle n = 1}$ u holda har qanday ikkita tepalikning sharti bo'sh joyni egallaydi va shu sababli barcha tepaliklar bir-biriga bog'lanib ${ displaystyle m ^ {2}}$ qirralar.
• Har bir tepada aniq bor ${ displaystyle m}$ kiruvchi va ${ displaystyle m}$ chiquvchi qirralar.
• Har biri ${ displaystyle n}$De Bruijn o'lchovli grafigi chiziqli grafik ning ${ displaystyle (n-1)}$- bir xil belgilar to'plamiga ega o'lchovli De Bryuyn grafigi.^[4]
• Har bir De Bruijn grafigi Evleriya va Hamiltoniyalik. Ushbu grafiklarning Eyler tsikllari va Gamilton davrlari (chiziqli grafika konstruktsiyasi orqali bir-biriga teng) De Bruijn ketma-ketliklari.

The chiziqli grafik quyida uchta eng kichik ikkitomonlama De Bruijn grafigi tasvirlangan. Rasmda ko'rinib turganidek, ning har bir tepasi ${ displaystyle n}$De Bruijn o'lchovli grafigi .ning chekkasiga to'g'ri keladi ${ displaystyle (n-1)}$- o'lchovli De Bruijn grafigi va har bir chekka ${ displaystyle n}$De-Bruijn o'lchovli grafigi ichidagi ikki qirrali yo'lga to'g'ri keladi ${ displaystyle (n-1)}$- o'lchovli De Bruijn grafigi.

Dinamik tizimlar

Ikkilik De Bruijn grafigini (quyida, chapda) shunday nazariyadagi narsalarga o'xshash tarzda chizish mumkin. dinamik tizimlar kabi Lorenz jalb qiluvchi (quyida, o'ngda):

Ushbu o'xshashlikni qat'iy qilish mumkin: n- o'lchovli m- belgi De Bruijn grafigi - ning modeli Bernulli xaritasi

${ displaystyle x mapsto mx { bmod {}} 1}$

Bernulli xaritasi (shuningdek 2x mod 1 xarita uchun m = 2) an ergodik yagona deb tushunish mumkin bo'lgan dinamik tizim siljish a m-adic soni.^[5] Ushbu dinamik tizimning traektoriyalari De Bruijn grafigidagi yurishlarga to'g'ri keladi, bu erda har bir haqiqiyni xaritalash orqali yozishmalar beriladi x [0,1) oralig'ida birinchisiga to'g'ri keladigan tepaga n raqamlari tayanch -m vakili x. Ekvivalent sifatida De Bruijn grafigida yurish bir tomonlama traektoriyalarga to'g'ri keladi chekli turdagi subshift.

Ikkala yo'naltirilgan grafikalar B (2, 3) de Bruijn ketma-ketliklari va a B (2, 4) ketma-ketlik. Bda (2,3). har bir tepaga bir marta tashrif buyuriladi, B (2,4) da esa har bir qirradan bir marta o'tadi.

Ikkala De Bruijn grafikalari borligini ko'rsatish uchun shunga o'xshash ko'milganlardan foydalanish mumkin navbat raqami 2^[6] va ular bor kitob qalinligi ko'pi bilan 5.^[7]

Foydalanadi

• Biroz tarmoq tarmog'i topologiyalar De Bruijn grafikalaridir.
• The tarqatilgan xash jadvali protokol Koorde De Bruijn grafikasidan foydalanadi.
• Yilda bioinformatika, De Bruijn grafikalari uchun ishlatiladi de novo yig'ilish ketma-ketlikni o'qiydi genom.^{[8][9][10][11][12]}

Shuningdek qarang

• De Bryuyn ketma-ketligi
• De Bruijn torus
• Hamming grafigi
• Kautz grafigi

Adabiyotlar

Tashqi havolalar

• Vayshteyn, Erik V. "De Bryuyn grafigi". MathWorld.
• Bioinformatikada De Bryuyn grafikalaridan foydalanish bo'yicha qo'llanma Homolog.us tomonidan