گراف دی براین

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

${\displaystyle 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})\}.}$

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

${\displaystyle 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}\}.}$

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

خصوصیات

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

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

ت

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

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

       

مطالعه شود

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

منابع

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.

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

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