گراف دی براین

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

در نظریه گراف، یک گراف دی براین بعدی از نماد، یک گراف جهت دار است که روی هم افتادگی توالی‌های نمادها را نشان می‌دهد. این گراف راس دارد و شامل تمام توالی‌های ممکن به طول n از نمادهای داده شده‌است. یک نماد ممکن است چندین بار در یک توالی ظاهر شود. اگر یک مجموعه از نماد داشته باشیم، یعنی ،آنگاه مجموعهٔ راس‌ها عبارت است از:

اگر یکی از راس‌ها بتواند به وسیلهٔ شیفت دادن نمادهای راسی دیگر به اندازهٔ یک مکان به چپ و اضافه کردن یک نماد جدید به انتهای آن بیان شود، آنگاه راس دوم یک یال جهت دار به راس اول خواهد داشت. به عبارت دیگر اگر پسوند راس دوم (شامل نماد) برابر پیشوند راس اول (شامل نماد) شود، آنگاه یک یال جهت دار از راس دوم به راس اول وجود خواهد داشت. بنابراین مجموعهٔ یال‌ها (جهت دار) عبارت است از:

اگرچه گراف‌های دی براین به نام نیکولا گواروت دی برویان نامگذاری شده است، اما این گرافها به طور مستقل توسط دی برویان[۱] و آی جی گود[۲] کشف شده‌اند. البته پیش از این کامیل فلای سینت ماری بصورت ضمنی از خواص این گراف‌ها استفاده کرده بود.[۳]

خصوصیات[ویرایش]

  • اگر باشد، آنگاه شرایط گفته شده برای هر دو راسی که باید تشکیل یال بدهند، بی معنی خواهد بود و تمام راس‌ها به وسیلهٔ یال به هم متصل خواهند بود.
  • هر راس دقیقاً یال ورودی و یال خروجی خواهد داشت.
  • هر گراف بعدی دی براین، یک گراف جهت دار خطی از گراف دی بر این بعدی با همان مجموعه نمادها است.
  • هر گراف دی بر این گراف اویلری یا گراف همیلتونی است. دور اویلری و دور همیلتونی در این گراف‌ها توالی دی براین را نشان می دهند.

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

DeBruijn-as-line-digraph.svg

سیستم های دینامیکی[ویرایش]

گراف‌های دی بر این دودویی می توانند به طریقی رسم شود که شبیه اشیاء نظریهٔ سیستم‌های دینامیکی باشند، مانند مجذوب کننده ی لورنز:

DeBruijn-3-2.svg         Lorenz attractor yb.svg

مطالعه شود[ویرایش]

منابع[ویرایش]

  1. de Bruijn; N. G. (1946). "A Combinatorial Problem". Koninklijke Nederlandse Akademie v. Wetenschappen. 49: 758–764.
  2. Good, I. J. (1946). "Normal recurring decimals". Journal of the London Mathematical Society. 21 (3): 167–169. doi:10.1112/jlms/s1-21.3.167.
  3. Flye Sainte-Marie, C. (1894). "Question 48". L'Intermédiaire des Mathématiciens. 1: 107–110.

ویکی‌پدیای انگلیسی

پیوند به بیرون[ویرایش]