المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۶:گراف:سوال ۳

گراف آزاد

گراف ‎$G$‎ با ‎$n$‎ رأس را در نظر بگیرید. فرض کنید که این گراف همبند است و همچنین ‎$K_{1,4}$‎ -آزاد می‎‌باشد (هیچ زیرگراف القایی دو بخشی کامل با یک رأس در یک بخش و چهار رأس در بخش دیگر ندارد.)

ثابت کنید این گراف یک تطابق به اندازه حداقل ‎$\lfloor \frac{n+1}{3} \rfloor$‎ دارد.


ابزار صفحه