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