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