گراف 3-منظم (3-Regular Graph)، در ریاضیات (Mathematics)
انواع گراف منتظم (Regular Graph) را در آموزش زیر شرح دادیم :
گراف 3-منظم (3-Regular Graph) :
گراف 3-منظم را با نام گراف مکعبی (Cubic Graph) نیز می شناسند. در این گراف ها، درجه هر راس برابر با 3 است. این گراف ها از اهمیت ویژه ای در نظریه گراف برخوردارند، زیرا ساده ترین حالت گراف های
\[ k \]-منظم با
\[ k>2 \]هستند که ساختارهای پیچیده و جالبی دارند.
برای مثال، گراف کامل با 4 راس (
\[ K_4 \]) یک گراف مکعبی است. همچنین، گراف Petersen (پترسن) مشهورترین مثال یک گراف مکعبی است که ویژگی های منحصربه فردی دارد. طبق قضیه هندشیکر-ویل ف (Handshaking Lemma)، مجموع درجات رئوس برابر با دو برابر تعداد یال هاست. بنابراین برای یک گراف مکعبی با
\[ n \]راس، تعداد یال ها برابر است با:
\[ \frac{3n}{2} \]این فرمول نشان می دهد که در یک گراف مکعبی، تعداد رئوس (
\[ n \]) باید حتما عددی زوج باشد.
نویسنده علیرضا گلمکانی
شماره کلید 5546
گزینه ها 
نظرات 0 0 0