Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۰:الگوریتم ها:سوال ۶

سوال ۶

گرافی با n راس داده شده است. به ما گفته شده که با حذف حداکثر k راس از این گراف می‌توان همه‌ی یال‌های گراف را حذف کرد. الگوریتمی با زمان O(2kn2) ارایه کنید که این کار را انجام دهد (یعنی حداکثر k راس را حذف کند تا همه‌ی یال‌ها حذف شوند)

اگر الگوریتمی با زمان اجرای O(22k2n2) ارائه کنید، نیمی از نمره را می‌گیرید.


ابزار صفحه