سلام
دوستان هر کسی میتونه این سوالو برام توضیح بده.
جواب گزینه ۱ است.
لینک سوالو پایین گذاشتم:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام.
درخت پوشای مینیموم رو در تصویر داده. اصل سوال رو بیایم اینطور در نظر بگیریم. بگیم که آیا اگر هریک از یال هایی که در ۴ گزینه سوال داده شده رو به گراف ابتدایی بدیم درختش همینی هست که رسم شده یا نه.
گزینه ۱/ یال بین گره ۴ و ۵ رو اگر فرض کنیم که وصل شده باشه، باز با پیمایش اول سطح درخت پوشای مینیموم حاصله همین درختی خواهد بود که رسم شده، چرا که در پیمایش اول سطح، اول ریشه، بعد به ترتیب فرزندان، بعد فرزند فرزندان و به همین صورت الی اخر(با رعایت ترتیب).
در این حالت هم ترتیب پیمایش بصورت ۱ ۲ ۳ ۴ ۵ ۶ ۷ هست. توجه کنید اگه یالی هم بلفرض بین ۴ و ۵ وجود داشته باشه، چون هردوی ۴ و ۵ فرزند ۲ هستند، پس با وجود (یا با وجود نداشتن) یال بین ۴ و ۵، پیمایش هیچ تغییری نمیکنه.
گزینه ۲/ در گزینه دوم میگه که گره شماره ۵، فرزند گره شماره یک باشه، پس با این حالت ترتیب پیمایش میشه ۱ ۲ ۵ ۳ ۴ ... (اما دیگه نباید یالی که ۲ رو به ۵ متصل کرده کشیده بشه، چرا که ۵ فرزند ۱ هست و در سومین عنصر پیمایش میشه. و این در تضاد با درخت رسم شده است).
گزینه ۳/ در این گزینه هم وقتی گره شماره ۴ فرزند گره شماره ۱ باشه، دیگه نیازی به رسم یال از ۲ به ۴ نیست، و این در تضاد با شکل هست.
گزینه ۴/ با توجه به گزینه ۲ رد خواهد شد.
ممنونم آقای احمدی
بسیار لطف کردید و خیلی عالی توضیح دادید.
از شما بینهایت سپاسگزارم.
موفق باشید.
