المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:تئوری نهایی دوم:سوال ۳

سوال ۳

گرافی ‎$n$‎ راسی به ما داده شده است. الگوریتمی با زمان چندجمله‌ای بر حسب ‎$n$‎ ارایه دهید که در این گراف یا خوشه‌ای به اندازه‌ی ‎$k$‎ بیابید یا گراف آقا جبل ‎۴ راسی (گراف نشان داده شده در شکل زیر). همچنین، اگر هیچکدام از این گراف‌ها نیز موجود نمی‌باشند، الگوریتم باید تشخیص دهد.


ابزار صفحه