سوال 46
حل تشریحی سوال شماره 46 دروس مشترک
کنکور ارشد مهندسی فناوری اطلاعات (IT) 1401
46.
گراف بدون وزن G شامل n راس و m یال داده شده است. هر یک از یالهای گراف با یکی از سه رنگ سبز، آبی و قرمز رنگآمیزی شده است. میخواهیم کوتاهترین مسیر از راس 1 به راس n را پیدا کنیم که رنگ هر دو یال مجاور در مسیر متفاوت باشد. در چه زمانی میتوان این کار را انجام داد؟ (بهترین گزینه را انتخاب کنید.)
1)
2)
برای این مسئله نمیتوان راهحل چند جملهای ارائه داد، مگر آنکه P=NP باشد.
3)
4)
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،