De Bruijn sequence¶
آیا می توان دور یک دایره \(2^n\) ارقام 0 و 1 نوشت به طوریکه اگر تمام بازه های متوالی به طول \(n\) را در نظر بگیریم کل اعداد باینری \(n\) بیتی را تولید کند؟
تبدیل به دور همیلتونی¶
اولین ایده ما برای مدل سازی این گراف به این شکل است :
یک گراف \(2^n\) راسی می سازیم که هر راس آن با یک رشته \(n\) تایی از 0 و 1 ها است. و راس \(a\) به راس \(b\) یال جهت دار دارد اگر بتوان رقم آخر رشته \(a\) را حذف کرد سپس یک حرف به اول آن اضافه کرد به طویکه رشته \(b\) حاصل شود. حالا سوال معادل با پیدا کردن یک دور همیلتونی در گرافی که ساختیم می باشد!
در اینجا به بن بست می خوریم زیرا که برای تشخیص اینکه یک گراف دور همیلتونی وجود دارد یا خیر روشی نداریم.
تبدیل به تور اویلری¶
یک گراف \(2^{n-1}\) راسی می سازیم که هر راس آن معادل با یک رشته \(n-1\) تایی از 0 و 1 ها است. هر راس مانند \(u\) دقیقا دو خروجی دارد. خروجی که عدد 0 روی آن نوشته شده است به راس \(w\) می رود به طوریکه اگر حرف آخر رشته \(u\) را حذف کنیم و به اول آن 0 را اضافه کنیم رشته حاصل همان رشته \(w\) خواهد بود. خروجی که روی آن عدد 1 نوشته شده است را هم می توان به شیوه مشابه تعریف کرد.
تفاوت اصلی گراف قبلی با این گراف این است که در گراف قبل هر بازه \(n\) تایی از 0 و 1 های دور دایره معادل با یک راس گراف بود. ولی در اینجا معادل با یک یال گراف است. و مسئله را به پیدا کردن تور اویلری در گراف تبدیل کردیم. (می توان ثابت کرد که همانطور که درجه خروجی هر راس 2 است درجه ورودی هر راس هم 2 است همچنین گراف زمینه همبند است پس گراف اویلری می باشد).
حالا اگر یک تور اویلری از گراف را پیدا کنید و ارقام روی یال های آن را به ترتیب دور دایره بنویسید چینش مطلوب ما حاصل خواهد شد!
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
