دو بخش‌کردن و رنگ‌آمیزی گراف
رنگ‌آمیزی گراف با دو رنگ: تشخیص دوپارچه بودن با BFS/DFS — کاربرد در تقسیم‌بندی و تطبیق
گراف دوپارچه (Bipartite)
گرافی که رئوسش را بتوان به دو گروه تقسیم کرد طوری که هر یال بین دو گروه باشد (داخل گروه یال نداشته باشیم). مثل دو تیم که فقط با حریف بازی می‌کنند!
تشخیص: رنگ‌آمیزی دو رنگ
گراف دوپارچه ⟺ با دو رنگ رنگ‌پذیر است. الگوریتم:
- BFS/DFS از هر رأس دیده‌نشده
- رنگ شروع = ۰؛ همسایه‌ها = ۱؛ همسایه‌های آن‌ها = ۰...
- اگر همسایه با «هم‌رنگ» پیدا شد ← دوپارچه نیست!
چرا جواب می‌دهد؟
دوپارچه نبودن ⟺ وجود دور فرد. رنگ‌آمیزی متناوب، دور فرد را «شکسته» نشان می‌دهد: آخرین و اولین هم‌رنگ می‌شوند — تناقض!
کاربردهای واقعی
| مسئله | دو گروه |
|---|---|
| دانشجو-درس | هیچ درسی دو دانشجوی هم‌گروه ندارد |
| خریدار-فروشنده | تطبیق بازار |
| تشخیص تعارض | زمان‌بندی بدون تداخل |
| شبکه‌های تبلیغاتی | دو طرف نمایشگاه |
پیچیدگی
O(V + E) — یک پیمایش BFS/DFS با آرایه رنگ.
نکته: رنگ‌آمیزی با k رنگ (k>2) NP-Complete است! فقط حالت دو رنگ، چندجمله‌ای و ساده است — این مرز ظریف را در مصاحبه بدانید.
جمع‌بندی
- دوپارچه = دو گروه بدون یال داخلی
- تشخیص: BFS با رنگ متناوب ۰/۱
- هم‌رنگی همسایه = دور فرد = نه دوپارچه
- کاربرد: تطبیق، زمان‌بندی، تعارض
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.