سوال 11
حل تشریحی سوال شماره 11 ساختمان داده ها و طراحی الگوریتم ها
کنکور دکتری مهندسی کامپیوتر 1401
11.
در مسئله "پوشش رأسی"، گراف ساده G=(V,E) و عدد صحیح K داده شده است و میخواهیم ببینیم "آیا زیر مجموعه با اندازه حداکثر k وجود دارد طوری که حداقل یک سر هر یال گراف G در C باشد؟" چند مورد از گزارههای زیر در خصوص این مسئله درست هستند؟
- مسئله پوشش رأسی ان پی - کامل است.
- مسئله پوشش راسی آن پی - سخت است.
- مسئله پوشش رأسی قابل کاهش به مسئله ۳SAT است.
- مسئلة SAT قابل کاهش به مسئله پوشش راسی است.
1)
1
2)
2
3)
3
4)
4
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،