المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳۲:سوالات ۱۹ و ۲۰

سوالات ۱۹ و ۲۰

گرافی با ۱۴۰۱ رأس و ۱۴۰۱ یال داریم که رأس‌های آن با اعداد ۱ تا ۱۴۰۱ شماره‌گذاری شده‌اند. به ازای هر $i$ ($1 \leq i \leq 1400$)، رأسهای $i$ و $i+1$ با یک یال به هم متصل هستند. رأس‌های با شماره‌های ۱ و ۱۴۰۱ نیز با یک یال به هم متصل هستند. به مجموعه‌ای از رأس‌ها مستقل گوییم اگر هیچ یالی بین رأس‌های آن وجود نداشته باشد. به مجموعه‌ی مستقل با بیش‌ترین اندازه، بزرگ‌ترین مجموعه مستقل گفته می‌شود.

با توجه به توضیحات بالا به ۲ سوال زیر پاسخ دهید.

سوال ۱۹

حداقل چند یال باید به گراف اضافه کنیم تا اندازه‌ی بزرگ‌ترین مجموعه مستقل آن حداقل یکی کم‌تر شود؟

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

سوال ۲۰

حداقل چند یال باید به گراف اضافه کنیم تا اندازه‌ی بزرگ‌ترین مجموعه مستقل آن حداقل دو تا کمتر شود؟

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

ابزار صفحه