المپدیا

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

ابزار کاربر

ابزار سایت


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

راس پر برکت

گراف دو بخشی $G$ با دو بخش $X$ و $Y$، تطابقی دارد که بخش $X$ را آلوده می‌کند. ثابت کنید این گراف راسی مثل $x$ دارد که هر کدام از یال‌های همسایه‌اش در حداقل یک تطابق بیشینه آمده است.


ابزار صفحه