رنگآمیزی رأسهای گراف؛ عدد رنگی و کرانها
آموزش رنگآمیزی درست رأسها، عدد رنگی، گراف دوبخشی و کرانهای سریع برای حل تستهای گراف.
پاسخ کوتاه
در رنگآمیزی درست، دو رأس مجاور نباید همرنگ باشند. هدف یافتن کمترین تعداد رنگ ممکن یا عدد رنگی گراف است. رسم منظم همسایگیها و شناخت ساختارهایی مانند دور، درخت و گراف کامل حل را سریع میکند.
رنگآمیزی درست
هر رأس یک رنگ میگیرد و دو سر هر یال باید رنگ متفاوت داشته باشند. رأسهای نامجاور میتوانند همرنگ باشند. نام رنگها اهمیت ندارد؛ فقط تعداد کلاسهای رنگ و سازگاری آنها با یالها مهم است.
عدد رنگی
عدد رنگی χ(G) کمترین تعداد رنگ برای یک رنگآمیزی درست است. داشتن یک رنگآمیزی با k رنگ فقط کران بالای χ را میدهد. برای اثبات کمینهبودن باید نشان دهیم با کمتر از k رنگ امکانپذیر نیست.
گراف کامل و دور
گراف کامل K_n به n رنگ نیاز دارد، چون هر دو رأس مجاورند. دور زوج با دو رنگ و دور فرد با سه رنگ رنگآمیزی میشود. همین دور فرد مانع دوبخشیبودن گراف است.
درخت و گراف دوبخشی
هر درخت با دستکم یک یال دورنگپذیر است؛ رأسها را بر اساس زوج یا فرد بودن فاصله از یک رأس ثابت تقسیم کن. بهطور کلی گراف بدون دور فرد دوبخشی و در صورت داشتن یال، عدد رنگی آن دو است.
مثال و تست کوتاه
گراف مثلث همان K_3 است و سه رنگ میخواهد. اگر یک رأس آویزان به یکی از رأسهای مثلث اضافه کنیم، عدد رنگی همچنان سه است؛ رأس تازه میتواند رنگ یکی از دو رأس غیرهمسایه خود را بگیرد.
چکلیست حل تست
- دو رأس مجاور نباید همرنگ باشند.
- دور فرد دستکم سه رنگ میخواهد.
- یک رنگآمیزی فقط کران بالا میدهد؛ کمینه را نیز ثابت کن.