جلسهی 25: رنگآمیزی گراف Colouring Graphs
رأسها را طوری رنگ کن که دو رأسِ وصلشده همرنگ نباشند. دورِ فرد ۳ رنگ میخواهد، گرافِ بدونِ دورِ فرد ۲ رنگ؛ برنامهی امتحانها با کمترین روز؛ و شمردنِ رنگآمیزیها.
در این جلسه یاد میگیری
- یک گراف را با کمترین تعداد رنگ رنگ میکنی.
- میدانی گراف با ۲ رنگ رنگ میشود اگر و فقط اگر دورِ فرد نداشته باشد.
- تعدادِ رنگآمیزیهای مسیر و دور را میشماری.
درس
پنج نقطه روی یک دایره، هر کدام به دو همسایهاش وصل. اول سعی کن با ۲ رنگ رنگشان کنی. نمیشود؟ چرا؟
با ۲ رنگ، دور یکدرمیان رنگ میشود: قرمز، آبی، قرمز، آبی، … دورِ ۵تایی بعد از ۵ قدم باید به رنگِ اول برگردد، ولی ۵ فرد است و رنگِ نقطهی پنجم با اولی یکی درمیآید. پس دورِ فرد ۳ رنگ میخواهد. با ۳ رنگ امتحان کن:
قانونِ مهم: یک گراف با ۲ رنگ رنگ میشود اگر و فقط اگر هیچ دورِ فردی نداشته باشد (به این گراف «دوبخشی» میگویند؛ مثلِ پسرها و دخترها وقتی فقط دوستیهای بینِ این دو گروه را داریم).
کاربرد: برنامهی امتحان. هر درس یک رأس؛ اگر یک دانشآموز هر دو درس را دارد، یالی بینشان. هر روز یک رنگ. کمترین تعدادِ روزها = کمترین تعدادِ رنگها.
شمردنِ رنگآمیزیها با k رنگ: یک مسیرِ n رأسی: رأسِ اول k انتخاب، هر رأسِ بعدی k − ۱ (فقط با قبلی فرق کند): k × (k − ۱)ⁿ⁻¹.
برای یک دور سختتر است، چون آخری باید با اولی هم فرق کند. برای دورِ ۵تایی با ۳ رنگ، جواب ۳۰ است: (k − ۱)ⁿ + (−۱)ⁿ(k − ۱) = ۳۲ − ۲.
اشتباه رایج: رنگآمیزیهایی که فقط با «عوض کردنِ اسمِ رنگها» فرق دارند هم متفاوت حساب میشوند، مگر سؤال چیز دیگری بگوید.
چالشها
- Two Colours (آسان)
- Which Needs Three? (آسان)
- The Wheel (متوسط)
- The Exam Timetable (متوسط)
- Colouring the House (سخت)
- A Ring of Five (سخت)
- Try It in Python: The Fewest Colours (سخت)