سوال 7
حل تشریحی سوال شماره 7 ساختمان داده
کنکور دکتری مهندسی کامپیوتر 1399
7.
برای گراف بدون جهت G با n رأس دو مسئله زیر را در نظر بگیرید:
- مسئله A : آیا G یک زیر مجموعه مستقل 4 رأسی دارد؟
- مسئله B : آیا G یک زیرمجموعه مستقل n-4 رأسی دارد؟
در خصوص این دو مسئله کدام مورد درست است؟
1)
مسئله A عضو کلاس P و مسئله B عضو کلاس NP-Complete است.
2)
مسئله A عضو کلاس NP-Complete و مسئله B عضو کلاس P است.
3)
هر دو مسئله عضو کلاس NP-Complete هستند.
4)
هر دو مسئله عضو کلاس P هستند.
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،