سوال 45
حل تشریحی سوال شماره 45 دروس مشترک
کنکور ارشد مهندسی فناوری اطلاعات (IT) 1398
45.
فرض کنید G یک گراف همبند جهت دار و وزن دار (با وزنهای مثبت) و یک عدد صحیح مثبت است. می خواهیم از یک رأس به رأس دیگر مسیری به وزن حداکثر (مجموع وزن یالهای مسیر حداکثر باشد) پیدا کنیم که تعداد رئوس میانی مسیر کمینه باشد. در این مورد کدام گزینه صحیح است؟
1)
یک مسئله ان پی - کامل است.
2)
یک مسئله ان پی - سخت است.
3)
در خروجی الگوریتم دایکسترا، تعداد رئوس میانی کمینه است.
4)
در زمان چند جملهای برحسب اندازه ورودی میتوان مسئله را حل کرد.
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،