سوالات المپیاد:مرحله ی اول:دوره ی ۲۷:سوال ۲
سوال ۲
می‌خواهیم رئوس گراف زیر را با قرمز و آبی رنگ کنیم. باید طوری این کار انجام شود که هر رأس (چه قرمز و چه آبی) دست‌کم یک رأس قرمز مجاور داشته باشد. توجه کنید در یک گراف دو رأس را
مجاور
گوییم، اگر با یک یال به هم وصل باشند. کمینه‌ی تعداد رأس‌های قرمز چیست؟
- ۳
- ۶
- ۲
- ۴
- ۵
پاسخ
گزینه‌ی ۳ درست است. با قرمز کردن تنها یک رأس نمی‌توان به هدف رسید، زیرا خود آن رأس، مجاور قرمز نخواهد داشت.
با قرمز کردن دو رأس به شکل زیر نیز کار انجام می‌شود.
پس پاسخ برابر ۲ است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
