المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:تئوری نهایی دوم:سوال ۳

سوال ۳

گرافی داریم که دور زوج ندارد و یال‌های آن ماکسیمال است. ثابت کنید اگر اندازه‌ی ماکسیمم مجموعه مستقل آن ‎$k$‎ باشد آن‌گاه ‎$\lceil n/3 \rceil \le k \le \lceil 2n/3‎ - ‎1 \rceil$‎ .


ابزار صفحه