المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۲۳:سوال ۳

سوال ۳

گرافی ۱۰۰ رأسی را در نظر بگیرد. می‌خواهیم بین بعضی از رئوس آن یال قرار دهیم به‌ طوری که بین هر دو رأس حداکثر یک یال باشد و اگر رأس‌ها را به هر روشی به دو بخش افراز کنیم، در حداقل یکی از بخش‌ها دور وجود داشته باشد. حداقل چند یال لازم داریم؟

  1. ۲۰
  2. ۱۰
  3. ۱۶
  4. ۲۲
  5. ۶

ابزار صفحه