گراف های دور با طول زوج (Even Cycle Graphs)، در ریاضیات (Mathematics)
انواع گراف دو بخشی (Bipartite Graph) را در آموزش زیر شرح دادیم :
گراف های دور با طول زوج (Even Cycle Graphs) :
گراف دور (Cycle Graph) با طول زوج، که با نماد
\[ C_n \](برای
\[ n \]زوج) نمایش داده می شود، یک گراف ساده است که رئوس آن در یک حلقه بسته قرار گرفته اند و هر رأس دقیقا به دو رأس همسایه خود متصل است. شرط دوبخشی بودن یک گراف این است که هیچ دوری به طول فرد (فرد) در آن وجود نداشته باشد .
بنابراین، یک گراف دور دو بخشی است اگر و فقط اگر تعداد رئوس آن زوج باشد . اگر تعداد رئوس فرد باشد، امکان رنگ آمیزی آن با دو رنگ بدون آن که دو رأس همرنگ مجاور هم شوند وجود ندارد (با شروع از یک رنگ، پس از طی کردن دور فرد به رأس شروع بازمی گردیم در حالی که باید همرنگ باشد، ولی مجاور است). این گراف ها در بررسی پدیده های تناوبی و سیستم های حلقوی کاربرد دارند.
نویسنده علیرضا گلمکانی
شماره کلید 5491
گزینه ها 
نظرات 0 0 0