المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۲۸:سوالات ۱۴ و ۱۵

سوالات ۱۴ و ۱۵

یک گراف ساده در نظر بگیرید که رأس های آن با قرمز و آبی رنگ شده اند. عمل سلطان‌پیچ روی گراف به این شکل انجام می شود که یک مجموعه از رأس ها مانند $S$ را انتخاب می کنیم، سپس رنگ هر راس خارج از $S$ را که به تعداد فردی از $S$ یال دارد، عوض می کنیم.

سوال ۱۴

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

  1. (آ)
  2. هر سه گراف
  3. هیچ کدام
  4. (آ) و (پ)
  5. (ب) و (پ)

پاسخ

سوال ۱۵

گراف های زیر از راست به چپ به ترتیب $2^6,2^7,2^7$ رنگ آمیزی اولیه‌ی ممکن دارند. در هر کدام به ترتیب از راست به چپ، به ازای چند رنگ آمیزی اولیه می توان با تعدادی عمل سلطان‌پیچ تمام راس ها را آبی کرد؟

  1. $112$
  2. $448$
  3. $224$
  4. $176$
  5. $56$

پاسخ


ابزار صفحه