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