المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:متفرقه:سوال ۵

راس‌های رنگی

گراف $G_n$ گرافی با راس‌های $a_1...a_{2n}$ که در آن راس $a_i$ به راس‌های $a_{i+1}$ و $a_{i+2}$ (در صورت وجود) وصل شده است (وصل بودن دوطرفه است). تمامی راس‌ها در ابتدا با رنگ قرمز رنگ شده‌اند. با انتخاب هر راس رنگ آن راس و تمام همسایه‌ها‌ی آن تغییر می‌کند (از آبی به قرمز و از قرمز به آبی). هر راس حداکثر می‌تواند یک بار انتخاب شود. به چند طریق می‌توان تعدادی از رئوس را انتخاب کرد به طوری که در پایان رنگ تمام رئوس آبی باشد؟


ابزار صفحه