سوالات المپیاد:دوره ی تابستان:دوره ی ۱۶:تئوری:سوال ۱۱
مهره‌ها
دو مسئله‌ی زیر را درنظر بگیرید:
مسئله‌ی A : گراف $G$ و تعدادی مهره روی بعضی رئوس آن داده شده است. می‌خواهیم مهره‌ها را روی یال‌ها طوری حرکت دهیم که زیرگراف القاییِ رئوسی که شامل حداقل یک مهره‌اند هم‌بند شده و مجموع حرکات مهره‌ها نیز کمینه بشود.
مسئله‌ی B : گراف دوبخشی $H$ که مجموعه‌ی رئوس دو بخش آن $X$ و $Y$ می‌باشند داده شده است. می‌خواهیم کوچک‌ترین زیرمجموعه‌ی $X$ مانند $S$ را پیدا کنیم به طوری که $N(S)=Y$.
ثابت کنید اگر برای مسئله‌ی $A$ الگوریتم چندجمله‌ای وجود داشته باشد برای مسئله‌ی $B$ نیز الگوریتم چندجمله‌ای وجود دارد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
