حل تشریحی سوال شماره 92 طراحی الگوریتم
کنکور ارشد مهندسی کامپیوتر 1399
92.
چند مورد از مسائل ان‌پی-سخت زیر هنگامی که ورودی یک درخت بدون وزن است. در زمان چند جمله‌ای قابل حل هستند؟
- پیدا کردن طولانی ترین مسیر
- محاسبه کمینه رنگ مورد نیاز برای رنگ امیزی راسی بطوری که رئوس مجاور همرنگ نباشند
- پیدا کردن بزرگترین مجموعه مستقل (مجموعه رئوسی که بین هر دو راس یالی وجود نداشته باشد)
1)
0
2)
1
3)
2
4)
3
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،