گراف دی براین

در نظریه گراف، یک گراف دی بروین $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$ بعدی با همان مجموعه نمادها است.
• هر گراف دی بروین گراف اویلری یا گراف همیلتونی است. دور اویلری و دور همیلتونی در این گراف‌ها توالی دی بروین را نشان می دهند.

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

ت

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

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

       

مطالعه شود

• دنباله دبروین

منابع

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