دنباله دبروین

طبق تعریف دنباله دبروین، ۲^n-1 واژهٔ دوتایی به طول n-۱ وجود دارد. گراف جهت داری با ۲^n-1 رأس را به شکل زیر می‌سازیم.

فرض می‌کنیم هر واژهٔ به طول n-۱ یک رأس باشد. از هر رأسی به صورت v=a_۱a_۲...a_n دو یال رسم می‌کنیم: یکی به سوی a_۲a_۳a_n-1۰ و دیگری به سوی a_۲a_۳a_n-1۱، تا نمایندهٔ دو واژهٔ n حرفی، به ترتیب، v۰ و v۱ باشند. از این رو، ۲ⁿ یال گراف جهت داری که از این طریق ساخته می‌شوند مجموعهٔ واژه‌های دوتایی به طول n را نمایش می‌دهند. این گراف جهت دار(۲،n)، که به گراف (جهت دار) دبروین مشهور است، ضیفاً همبند و اویلری است؛ زیرا درجهٔ ورودی هر رأس برابر با درجهٔ خروجی آن است.

شکل:

بطور کلی، برای الفبایی مرکب از p حرف، G(p,n) گراف جهت دار دبروینی با p^n-1 رأس و pⁿ کمان است؛ به‌طوری‌که درجهٔ ورودی و درجهٔ خروجی هر رأس برابر با p است. G(p,n)، یک گراف اویلری است. حال مسیر بستهٔ اویلری دلخواهی را در این گراف جهت دار در نظر می‌گیریم که دنباله وار شامل همهٔ این pⁿ کمان باشد و دنبالهٔ حروف نخست همهٔ این واژه‌ها را می‌سازیم. این دنباله را با a_۱a_۲...a_r، که در آن pⁿ = r، نشان می‌دهیم. آنگاه همهٔ این r واژهٔ متمایز به طول n به صورت a_ia_i+1...a_i+n-۱اند که در آن عمل جمع تعریف شده روی اندیسها به پیمانهٔ r است.

مثلاً، اگر p=۲ و n=۳، آنگاه a_۹ همان a_۱ است. در گراف جهت دار … مدار اویلری جهت داری مه از ۰۰ شروع می‌شود مرکب از دنبالهٔ هشت کمان بعدی است: ۰۰۰، ۰۰۱، ۰۱۱، ۱۱۱، ۱۱۰، ۱۰۱، ۰۱۰، ۱۰۰. حروف نخست این کمان‌ها واژهٔٔ ۰۰۰۱۱۱۰۱ را می‌سازند که در نتیجه a_۸ = ۰، a_۷ = ۰، a_۶ = ۰، a_۵ = ۰، a_۴ = ۰، a_۳ = ۰، a_۲ = ۰، a_۱ = ۰.

اینک هر واژهٔ سه حرفی به صورت a_i a_i+1 a_i+2 است:

a۷ a۸ a۹ = a۷ a۸ a۱ = ۰۱۰ و غیره.

می‌توانیم به ازای دو عدد صحیح مثبت p و n یک دنبالهٔ دبروین را به‌طور صوری تعریف کنیم. اگر S الفبایی مرکب از p حرف باشد، آنگاه دنباله‌ای مانند a_۱a_۲...a_r از (r = pⁿ)r حرف را دنبالهٔ دبروین می‌نامند و آن را با B(p,n) نشان می‌دهند هرگاه، بتوان هر واژهٔ به طول n مرکب از حروف S را به صورت aⁱaⁱ⁺¹...a^i+n-۱ درآورد که در آن عمل جمع بین اندیس‌ها به پیمانهٔ r است.

طول هر B=(p,n) برابر pⁿ است.

به ازای هر B=(p,n)، k! k (n − ۱)/kn دنبالهٔ دبروین متمایز وجود دارد.

به ازای هر جفت از اعداد صحیح مثبت، یک دنبالهٔ دبروین وجود دارد. این قضیه را نخست دبروان (۱۹۴۶) به ازای p=۲ ثابت کرد و سپس گود(۱۹۴۶) آن را به ازای p دلخواهی تعمیم داد.

این دنباله‌ها در نظریهٔ کدگذاری بسیار سودمندند. نمودار حالت یک ثبات انتقالی بازخوردی (FSR) زیرگراف گراف دبروین مشخصی است. FSRها به ویژه به سبب خواص تصادفی دنباله‌هایی که پدید می‌آورند کاربردهای وسیعی در مخابرات، رمزنگاری و علم کامپیوتر دارند.

همچنین در حمله جستجوی فراگیر (Brute-force attack) می‌توان برای کوتاه کردن کدهایی استفاده کرد که دکمهٔ Enter نداشته و n حرف آخر را به عنوان رمز درست قبول می‌کنند. بری مثال، برای رمزگشایی یک در دیجیتالی با رمز ۴ رقمی، (۱۰٬۴)B حالت مختلف وجود دارد. یعنی حداکثر ۱۰۰۰۰ + ۳ = ۱۰۰۰۳ دکمه را باید فشار دهیم (دنباله چرخشی است). در حالیکه امتحان جداگانهٔ تمام کدها به ۴*۱۰۰۰۰ = ۴۰۰۰۰ بار فشار دادن دکمه نیاز دارد.

از دیگر کاربردهای دنبالهٔ دبروین، یافتن سریع اولین و آخرین بیت از یک کلمه، و همچنین کد گری است.

• http://en.wikipedia.org/wiki/De_Bruijn_graph
• http://en.wikipedia.org/wiki/De_Bruijn_sequence