المپدیا

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

ابزار کاربر

ابزار سایت


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

مهره‌ها

‎ دو مسئله‌ی زیر را درنظر بگیرید:

مسئله‌ی A‎‎ : گراف ‎$G$‎ و تعدادی مهره روی بعضی رئوس آن داده شده است. می‌خواهیم مهره‌ها را روی یال‌ها طوری حرکت دهیم که زیرگراف القاییِ رئوسی که شامل حداقل یک مهره‌اند هم‌بند شده و مجموع حرکات مهره‌ها نیز کمینه بشود.

مسئله‌ی B : گراف دوبخشی ‎$H$‎ که مجموعه‌ی رئوس دو بخش آن ‎$X$‎ و ‎$Y$‎ می‌باشند داده شده است. می‌خواهیم کوچک‌ترین زیرمجموعه‌ی ‎$X$‎ مانند ‎$S$‎ را پیدا کنیم به طوری که ‎$N(S)=Y$‎.

ثابت کنید اگر برای مسئله‌ی ‎ $A$‎ الگوریتم چندجمله‌ای وجود داشته باشد برای مسئله‌ی ‎ $B$ نیز الگوریتم چندجمله‌ای وجود دارد.


ابزار صفحه