المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۶:سوال ۵

سوال ۵

به گراف ۱۶ رأسی $G$ گراف فرد زده گوییم، اگر هر رأس آن هم در دوری به طول ۳ و هم در دوری به طول ۵ و … و هم در دوری به طول ۱۵ باشد. حال فرض کنید یک گراف دوبخشی کامل داریم که هر بخش آن ۸ رأس دارد. می‌خواهیم تعدادی یال به این گراف اضافه کنیم تا فرد زده شود. حداقل چند یال باید اضافه کنیم؟

  1. $1$
  2. $2$
  3. $8$
  4. $16$
  5. $28$

پاسخ

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

برای این‌که همه‌ی رئوس یک بخش در یک مثلث باشند باید حداقل یک یال در بخش دیگر قرار داد (و یا چهار یال در همان بخش قرار دهیم). در نتیجه حداقل ۲ یال لازم است. ولی چون گراف کامل دو بخشی است و از هر راسی به هر راس در بخش مقابل یال وجود دارد، با اضافه کردن این دو یال تمامی دورهای فرد راسی را می‌توان ساخت.


ابزار صفحه