رنگآمیزی گراف
رنگآمیزی گراف با کمترین تعداد رنگ ممکن
دربارهٔ این ماشینحساب
ماشینحساب رنگآمیزی گراف عدد رنگی χ(G) — کمترین تعداد رنگی که برای رنگآمیزی رأسهای گراف لازم است به طوری که هیچ یالی دو رأس همرنگ را به هم وصل نکند — را پیدا میکند و یک رنگآمیزی بهینه نشان میدهد. تعداد رأسها و فهرستی از یالها را وارد کنید؛ χ را با جستوجوی شاخه و کران به طور دقیق محاسبه میکند، بیشینهٔ درجه Δ و بزرگترین خوشه ω (یک کران پایین برای χ) را گزارش میکند، گرافهای دوبخشی و کامل را مشخص میکند و گراف رنگآمیزیشده را رسم میکند. مناسب برای زمانبندی، تخصیص ثبات، رنگآمیزی نقشه و مطالعهٔ اعداد رنگی.
روش رنگآمیزی گراف
- تعداد رأسها را وارد کنید؛ آنها از 1 تا n شمارهگذاری میشوند.
- یالها را به صورت جفتهایی مانند 1-2, 2-3 فهرست کنید — یک جفت برای هر اتصال.
- عدد رنگی χ(G) و رنگ اختصاصیافته به هر رأس را بخوانید.
- χ را با بزرگترین خوشه ω مقایسه کنید تا ببینید چرا این تعداد رنگ لازم است، یا برای کاوش یک پیشتنظیم را بارگذاری کنید.
نمونههای رایج
- مثلث (K₃) به 3 رنگ نیاز دارد — هر دو رأس آن با هم مجاورند.
- دورهای زوج دوبخشیاند و فقط به 2 رنگ نیاز دارند؛ دورهای فرد مانند C₅ به 3 رنگ نیاز دارند.
- گراف کامل Kₙ دقیقاً به n رنگ نیاز دارد.
- بزرگترین خوشه با اندازهٔ ω دستکم ω رنگ را الزامی میکند، پس χ(G) ≥ ω.
- گراف گروتچ به 4 رنگ نیاز دارد اما هیچ مثلثی ندارد، پس χ میتواند از عدد خوشه بیشتر باشد.
پرسشهای متداول
عدد رنگی چیست؟
عدد رنگی χ(G) کمترین تعداد رنگی است که برای رنگآمیزی رأسهای یک گراف لازم است، به طوری که هیچ یالی دو رأس همرنگ را به هم وصل نکند.
کمترین تعداد رنگ چگونه پیدا میشود؟
چون گراف کوچک است، ماشینحساب به طور دقیق جستوجو میکند: 1 رنگ را امتحان میکند، سپس 2 و همینطور ادامه میدهد و اولین تعدادی را که برای آن رنگآمیزی سرهای وجود دارد برمیگرداند. تضمین میشود که این تعداد همان کمینهٔ واقعی است.
بیشینهٔ درجه و بزرگترین خوشه چیستند؟
بیشینهٔ درجه Δ بیشترین تعداد یالهایی است که به یک رأس میرسند. بزرگترین خوشه ω بزرگترین مجموعه از رأسهایی است که همه دوبهدو با هم مجاورند؛ چون همهٔ آنها باید رنگ متفاوت داشته باشند، χ(G) دستکم برابر ω است.
چرا یک گراف بدون مثلث هم ممکن است به رنگهای زیادی نیاز داشته باشد؟
یک خوشهٔ بزرگ رنگهای زیادی را الزامی میکند، اما تنها دلیل نیست. دورهای فرد و گرافهایی مانند گراف گروتچ حتی بدون هیچ مثلثی به رنگهای بیشتری نیاز دارند، پس χ(G) میتواند از عدد خوشه بزرگتر باشد.
آیا اندازهٔ گراف محدودیتی دارد؟
بله. رنگآمیزی دقیق گراف از نظر محاسباتی دشوار است، بنابراین ماشینحساب اندازهٔ گراف را به 12 رأس محدود میکند تا نتایج فوری و دقیق بمانند.