المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۳

‎$G$‎، گرافی ‎$n$‎ رأسی با یال‌های ‎$e_1‎, ‎e_2‎, ‎\dots‎, ‎e_m$‎ است. می‌خواهیم تعدادی زیرگراف دوبخشی کامل فراگیر از ‎$G$‎ پیدا کنیم که هر یال ‎$e_i$‎ حداقل در یکی از این زیرگراف‌ها آمده باشد.

الگوریتمی چندجمله‌ای ارائه دهید که بگوید آیا می‌توان این کار را انجام داد یا نه، و اگر می توان حداقل چند زیرگراف لازم است؟


ابزار صفحه