در علم ریاضی گراف مکعبی، گرافی است که تمام رأس های آن دارای درجهٔ ۳ باشد یا به زبان دیگر می توان گفت گراف مکعبی یک گراف ۳ - منتظم است.
همچنین یک گراف دو مکعبی یک گراف دو بخشی است.
در سال 1932 Ronald M. Foster به دنبال جمع آوری گراف های مکعبی متقارن بود
نمونه هایی از گراف های مکعبی می توان به: utility graph, گراف پترسن, گراف هی وود، Möbius–Kantor graph, the Pappus graph, Desargues graph, Nauru graph, Coxeter graph, Tutte–Coxeter graph, Dyck graph, Foster graph , Biggs - Smith graph. ویلیام توماس تات اشاره کرد.
گراف های مکعبی نیمه متقارن شامل گراف های Gray graph ( که کوچکترین گراف مکعبی متقارن است ) , Ljubljana graph و Tutte 12 - cage می باشد.
Frucht graph یکی از دو گراف مکعبی متقارن می باشد؛ که این گراف شامل یک graph automorphism که باعث شده هویت گراف های اتو مورفیسم را داشته باشد.
براساس تئوری بروکس هر گراف مکعبی همبند به جز دستهٔ گراف های کامل K4 می تواند با حداقل ۳ رنگ رنگ آمیزی شود. پس هر گراف مکعبی همبند به جز گراف K4 دارای یک مجموعه مستقل از حداقل n/3 رأس ها می باشد که در واقع n تعداد رأس های گراف است. به طور مثال بزرگترین کلاس رنگ ۳ تایی دست کم این تعداد راس را دارا می باشند.
براساس تئوری ویزینگ هر گراف مکعبی نیازمند ۳ یا ۴ رنگ برای رنگ آمیزی یال ها می باشد. گراف هایی که نیازمند ۳ رنگ برای رنگ آمیزی یال های آن هستیم به رنگ آمیزی تیت ( tait ) معروف هستند. حال براساس تئوری کونیگ هر گراف دوبخشی دارای رنگ آمیزی تیت می باشد.
گراف های کم یال مکعبی که رنگ آمیزی تیت را ندارند به نام اسنارک شناخته می شوند. به طور مثال می توان به گراف پترسن، Blanuša snarks, flower snark, double - star snark, Szekeres snark وWatkins snark. تعداد نامحدودی از گراف های اسنارک موجود می باشد.
گراف های مکعبی به صورت طبیعی در توپولوژِ در راه های مختلفی به وجود می آیند. به طور مثال اگر یک نفر تصمیم بگیرد یک گراف که یک بعدی باشد بسازد به راحتی می تواند این کار را انجام دهد.
تحقیقات زیادی بر بروی همیلتونی بودن گراف های مکعبی می باشد. در سال 1880 P. G. Tait حدس زد که هر گراف مکعبی پلی هدرال یک دور همیلتونی دارد. ویلیام توماس تات مثال های زیادی برای رنگ آمیزی با روش تیت و حدس های زده شده توسط پیتر زد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفهمچنین یک گراف دو مکعبی یک گراف دو بخشی است.
در سال 1932 Ronald M. Foster به دنبال جمع آوری گراف های مکعبی متقارن بود
نمونه هایی از گراف های مکعبی می توان به: utility graph, گراف پترسن, گراف هی وود، Möbius–Kantor graph, the Pappus graph, Desargues graph, Nauru graph, Coxeter graph, Tutte–Coxeter graph, Dyck graph, Foster graph , Biggs - Smith graph. ویلیام توماس تات اشاره کرد.
گراف های مکعبی نیمه متقارن شامل گراف های Gray graph ( که کوچکترین گراف مکعبی متقارن است ) , Ljubljana graph و Tutte 12 - cage می باشد.
Frucht graph یکی از دو گراف مکعبی متقارن می باشد؛ که این گراف شامل یک graph automorphism که باعث شده هویت گراف های اتو مورفیسم را داشته باشد.
براساس تئوری بروکس هر گراف مکعبی همبند به جز دستهٔ گراف های کامل K4 می تواند با حداقل ۳ رنگ رنگ آمیزی شود. پس هر گراف مکعبی همبند به جز گراف K4 دارای یک مجموعه مستقل از حداقل n/3 رأس ها می باشد که در واقع n تعداد رأس های گراف است. به طور مثال بزرگترین کلاس رنگ ۳ تایی دست کم این تعداد راس را دارا می باشند.
براساس تئوری ویزینگ هر گراف مکعبی نیازمند ۳ یا ۴ رنگ برای رنگ آمیزی یال ها می باشد. گراف هایی که نیازمند ۳ رنگ برای رنگ آمیزی یال های آن هستیم به رنگ آمیزی تیت ( tait ) معروف هستند. حال براساس تئوری کونیگ هر گراف دوبخشی دارای رنگ آمیزی تیت می باشد.
گراف های کم یال مکعبی که رنگ آمیزی تیت را ندارند به نام اسنارک شناخته می شوند. به طور مثال می توان به گراف پترسن، Blanuša snarks, flower snark, double - star snark, Szekeres snark وWatkins snark. تعداد نامحدودی از گراف های اسنارک موجود می باشد.
گراف های مکعبی به صورت طبیعی در توپولوژِ در راه های مختلفی به وجود می آیند. به طور مثال اگر یک نفر تصمیم بگیرد یک گراف که یک بعدی باشد بسازد به راحتی می تواند این کار را انجام دهد.
تحقیقات زیادی بر بروی همیلتونی بودن گراف های مکعبی می باشد. در سال 1880 P. G. Tait حدس زد که هر گراف مکعبی پلی هدرال یک دور همیلتونی دارد. ویلیام توماس تات مثال های زیادی برای رنگ آمیزی با روش تیت و حدس های زده شده توسط پیتر زد.
wiki: گراف مکعب