پرش به محتوا

گراف دی براین

از ویکی‌پدیا، دانشنامهٔ آزاد

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

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

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

خصوصیات

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

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

ت
ت

سیستم های دینامیکی

[ویرایش]

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

       

مطالعه شود

[ویرایش]

منابع

[ویرایش]
  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.

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

پیوند به بیرون

[ویرایش]