گراف دی براین

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

در نظریه گراف، یک گراف دی براین nبعدی از m نماد، یک گراف جهت دار است که روی هم افتادگی توالی های نماد ها را نشان می دهد. این گراف m^n راس دارد و شامل تمام توالی های ممکن به طول n از نماد های داده شده است. یک نماد ممکن است چندین بار در یک توالی ظاهر شود. اگر یک مجموعه از m نماد داشته باشیم، یعنی S:=\{s_1,\dots,s_m\} ،آنگاه مجموعه ی راس ها عبارت است از:

V=S^n=\{(s_1,\dots,s_1,s_1),(s_1,\dots,s_1,s_2),\dots,(s_1,\dots,s_1,s_m),(s_1,\dots,s_2,s_1),\dots,(s_m,\dots,s_m,s_m)\}.

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

E=\{((v_1,v_2,\dots,v_n),(w_1,w_2,\dots,w_n)) : v_2=w_1,v_3=w_2,\dots,v_n=w_{n-1}\}.

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

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

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

DeBruijn-as-line-digraph.svg

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

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

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

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

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

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

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