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

در ترکیبیات، به دنباله‌ای با درجه n از ۰ و ۱، دنباله دبروین می‌گویند که طول برابر است با ۲ n .
این دنباله به افتخار ریاضیدان هلندی، نیکلاس گاورت دبروین، نامگذاری شده‌است. این دنباله تشکیل شده از زیردنباله‌های n حرفی از ۰ و ۱ که هر کدام از این زیردنباله‌ها به عنوان یک کاراکتر در نظر گرفته می‌شوند.
مثلا به ازای n=۳ زیردنباله‌های دبروین را به این صورت خواهیم داشت: ۰۰۰،۰۰۱،۰۱۰،۱۰۰،۰۱۱،۱۰۱،۱۱۰،۱۱۱ و هر کلمه ۸ حرفی متشکل از ۰ و ۱ را می‌توان به کمک این ۸ واژه ساخت. نمایش این دنباله (واژه)ها به کمک گراف دبروین که یکی از کاربردهای گراف‌های جهت دار اویلری است انجام می‌شود.
گراف دبروین دوتایی
طبق تعریف دنباله دبروین، ۲ 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 را نمایش می‌دهند. این گراف جهت دار(۲،n)، که به گراف (جهت دار) دبروین مشهور است، ضیفا همبند و اویلری است؛ زیرا درجه ورودی هر راس برابر با درجه خروجی آن است.
شکل:
تعریف کلی گراف دبروین
بطور کلی، برای الفبایی مرکب از p حرف، G(p,n) گراف جهت دار دبروینی با p n-1 راس و p n کمان است؛ به‌طوری‌که درجه ورودی و درجه خروجی هر راس برابر با p است. G(p,n)، یک گراف اویلری است. حال مسیر بسته اویلری دلخواهی را در این گراف جهت دار در نظر می‌گیریم که دنباله وار شامل همه این p n کمان باشد و دنباله حروف نخست همه این واژه‌ها را می‌سازیم. این دنباله را با a ۱ a ۲ …a r ، که در آن p n = r، نشان می‌دهیم. آنگاه همه این r واژه متمایز به طول n به صورت a i a 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 n )r حرف را دنباله دبروین می‌نامند و آن را با B(p,n) نشان می‌دهند هرگاه، بتوان هر واژه به طول n مرکب از حروف S را به صورت a i a i+1 …a i+n-۱ درآورد که در آن عمل جمع بین اندیس‌ها به پیمانه r است.
طول هر B=(p,n) برابر p n است.
به ازای هر B=(p,n)، k! k (n − ۱)/kn دنباله دبروین متمایز وجود دارد.
قضیه
به ازای هر جفت از اعداد صحیح مثبت، یک دنباله دبروین وجود دارد. این قضیه را نخست دبروان (۱۹۴۶) به ازای p=۲ ثابت کرد و سپس گود(۱۹۴۶) آن را به ازای p دلخواهی تعمیم داد.
کاربردها
این دنباله‌ها در نظریه کدگذاری بسیار سودمندند. نمودار حالت یک ثبات انتقالی بازخوردی (FSR) زیرگراف گراف دبروین مشخصی است. FSRها به ویژه به سبب خواص تصادفی دنباله‌هایی که پدیدمی‌آورند کاربردهای وسیعی در مخابرات، رمزنگاری و علم کامپیوتر دارند.
همچنین در حمله جستجوی فراگیر (Brute-force attack) می‌توان برای کوتاه کردن کدهایی استفاده کرد که دکمه Enter نداشته و n حرف آخر را به عنوان رمز درست قبول می‌کنند. بری مثال، برای رمزگشایی یک در دیجیتالی با رمز ۴ رقمی، (۱۰،۴)B حالت مختلف وجود دارد. یعنی حداکثر ۱۰۰۰۰ + ۳ = ۱۰۰۰۳ دکمه را باید فشار دهیم (دنباله چرخشی است). در حالیکه امتحان جداگانه تمام کدها به ۴*۱۰۰۰۰ = ۴۰۰۰۰ بار فشار دادن دکمه نیاز دارد.
از دیگر کاربردهای دنباله دبروین، یافتن سریع اولین و آخرین بیت از یک کلمه، و همچنین کد گری است.