گراف دی براین

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

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

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

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

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

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

DeBruijn-as-line-digraph.svg

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

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

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

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

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

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

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