المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۲۹:سوالات ۱۶ و ۱۷

سوالات ۱۶ و ۱۷

سال‌ها پیش فردی به نام پترسن گراف زیر را از صندوق‌چه‌ی سلطان دزدید و به نام خود زد!

سلطان دلش برای این گراف تنگ شده است و می‌خواهد اندکی با آن بازی کند! او در ابتدا رأس‌های گراف را با قرمز و آبی رنگ می‌کند. سپس هر مرحله به طور هم‌زمان رنگ هر رأس را برابر با رنگی قرار می‌دهد که در همسایه‌هایش بیش‌تر تکرار شده است.

سوال ۱۶

سلطان در ابتدا به چند طریق می‌تواند سه رأس را قرمز و بقیه را آبی کند، طوری که هم‌واره حداقل یک رأس قرمز در گراف باقی بماند؟ رأس‌های گراف را متمایز در نظر بگیرید.

  1. ۲۰
  2. ۵
  3. ۱۲۰
  4. ۳۰
  5. ۱۲

پاسخ

گزینه (۱) درست است.

سوال ۱۷

کمینه‌ی $k$ را بیابید، طوری که سلطان در ابتدا به هر روشی که $k$ رأس را قرمز و بقیه را آبی کند، هم‌واره دست کم یک رأس قرمز در گراف باقی بماند.

  1. ۳
  2. ۴
  3. ۵
  4. ۶
  5. ۷

پاسخ

گزینه (۳) درست است.


ابزار صفحه