گراف دی براین

در نظریه گراف، یک گراف دی بروین ${\displaystyle n}$

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

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