گراف مکعبی (Cubic Graph)، در ریاضیات (Mathematics)
انواع گراف ساده (Simple Graph) را در آموزش زیر شرح دادیم :
گراف مکعبی (Cubic Graph) :
گراف مکعبی یا ۳-منتظم (3-Regular Graph) به گرافی گفته می شود که درجه تمام رأس های آن برابر با ۳ باشد. به عبارت دیگر، هر رأس دقیقا با سه رأس دیگر همسایه است. این گراف ها زیرمجموعه ای از گراف های منتظم (Regular Graphs) هستند. مفهوم "منتظم" به این معناست که همه رأس ها درجه یکسانی دارند. در یک گراف مکعبی، طبق لم دست فشانی (Handshaking Lemma)، مجموع درجه ها (
\[ 3n \]) باید زوج باشد، بنابراین تعداد رأس ها (
\[ n \]) در این گراف ها حتما زوج است. معروف ترین مثال از گراف های مکعبی، گراف پیترسن (Petersen Graph) با ۱۰ رأس و ۱۵ یال است. این گراف ها در معماری شبکه های موازی و طراحی چیپ های کامپیوتری به دلیل تقارن و ویژگی های ارتباطی خاص خود مورد توجه قرار گرفته اند. پیدا کردن و طبقه بندی گراف های مکعبی یک شاخه فعال در نظریه گراف است.
\[ 3\text{-regular graph: } \forall v \in V, \deg(v) = 3 \]