بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 25: رنگ‌آمیزی گراف Colouring Graphs

رأس‌ها را طوری رنگ کن که دو رأسِ وصل‌شده هم‌رنگ نباشند. دورِ فرد ۳ رنگ می‌خواهد، گرافِ بدونِ دورِ فرد ۲ رنگ؛ برنامه‌ی امتحان‌ها با کمترین روز؛ و شمردنِ رنگ‌آمیزی‌ها.

در این جلسه یاد می‌گیری

درس

پنج نقطه روی یک دایره، هر کدام به دو همسایه‌اش وصل. اول سعی کن با ۲ رنگ رنگشان کنی. نمی‌شود؟ چرا؟

با ۲ رنگ، دور یک‌در‌میان رنگ می‌شود: قرمز، آبی، قرمز، آبی، … دورِ ۵تایی بعد از ۵ قدم باید به رنگِ اول برگردد، ولی ۵ فرد است و رنگِ نقطه‌ی پنجم با اولی یکی درمی‌آید. پس دورِ فرد ۳ رنگ می‌خواهد. با ۳ رنگ امتحان کن:

قانونِ مهم: یک گراف با ۲ رنگ رنگ می‌شود اگر و فقط اگر هیچ دورِ فردی نداشته باشد (به این گراف «دوبخشی» می‌گویند؛ مثلِ پسرها و دخترها وقتی فقط دوستی‌های بینِ این دو گروه را داریم).
کاربرد: برنامه‌ی امتحان. هر درس یک رأس؛ اگر یک دانش‌آموز هر دو درس را دارد، یالی بینشان. هر روز یک رنگ. کمترین تعدادِ روزها = کمترین تعدادِ رنگ‌ها.

شمردنِ رنگ‌آمیزی‌ها با k رنگ: یک مسیرِ n رأسی: رأسِ اول k انتخاب، هر رأسِ بعدی ⁦k − ۱⁩ (فقط با قبلی فرق کند): ⁦k × (k − ۱)ⁿ⁻¹⁩.
برای یک دور سخت‌تر است، چون آخری باید با اولی هم فرق کند. برای دورِ ۵تایی با ۳ رنگ، جواب ۳۰ است: ⁦(k − ۱)ⁿ + (−۱)ⁿ(k − ۱) = ۳۲ − ۲⁩.
اشتباه رایج: رنگ‌آمیزی‌هایی که فقط با «عوض کردنِ اسمِ رنگ‌ها» فرق دارند هم متفاوت حساب می‌شوند، مگر سؤال چیز دیگری بگوید.

چالش‌ها

  1. Two Colours (آسان)
  2. Which Needs Three? (آسان)
  3. The Wheel (متوسط)
  4. The Exam Timetable (متوسط)
  5. Colouring the House (سخت)
  6. A Ring of Five (سخت)
  7. Try It in Python: The Fewest Colours (سخت)

← جلسه‌ی 24: درخت جلسه‌ی 26: آزمون آزمایشیِ کامل ۱ →