سوال 93

حل تشریحی سوال شماره 93 طراحی الگوریتم

کنکور ارشد مهندسی کامپیوتر 1399

93.

گراف همبند و وزن‌دار G را در نظر بگیرید. درخت پوشای کمینه G لزوما یکتا نیست و G میتواند چندین درخت پوشای کمینه داشته باشد. فرض کنید T یک درخت پوشای کمینه دلخواه از G باشد. کدام یک از گزاره‌های زیر درست هستند؟

الف) حتما یک اجرا از الگوریتم پریم وجود دارد که T را تولید کند

ب) حتما یک اجرا از الگوریتم کروسکال وجود دارد که T را تولید کند

توجه کنید زمانی که وزن یال‌ها متماز نیست، میتوان اجراهای متفاوتی برای هر دو الگوریتم پریم و کروسکال در نظر گرفت. در واقع وقتی چندین یال دارای وزن یکسان باشند، میتوان هر ترتیبی از انها را برای پردازش مورد نظر الگوریتم‌های فوق در نظر گرفت.

1)

الف درست، ب درست

2)

الف درست، ب نادرست

3)

الف نادرست، ب درست

4)

الف نادرست، ب نادرست

پاسخ ها

0 پاسخ
تا کنون پاسخی برای این سوال وارد نشده است،

ارسال پاسخ