(۰۵ اردیبهشت ۱۳۹۵ ۰۲:۱۷ ب.ظ)naserqw نوشته شده توسط:  سلام
تو آزمون جامع مدرسان شماه ۹ سوالی مطرح شده با عنوان زیر
g یک گراف بدون جهت است که n راس دارد. می خواهیم بزرگ ترین مجموعه از ریوس گراف g را بیابیم که بین هیچ دو راس از این مجموعه یالی وجود نداشته باشد. حداقل مرتبه زمانی برای یافتن چنین مجموعه ای در گراف g با n راس چقدر است؟؟
بگم که مثله این سوال تو ۶۰۰ مسیله قدسی سوال ۶/۶۲ فصل گرا اومده با عنوان مجموعه تنفر داشتن افراد و گفته میشه تو V^2 جواب رو پیدا کرد. ولی مدرسان گفته NP-complate هست.
یه نفر منو روشن کنه.
ممنونم