(۲۰ بهمن ۱۳۹۱ ۰۲:۴۱ ب.ظ)mohammadjavadkho نوشته شده توسط: (20 بهمن ۱۳۹۱ ۰۱:۰۱ ق.ظ)mohsen.srn نوشته شده توسط: برای سوال ۴۸ این گرافی رو که گذاشتم در نظر بگیرید.
یال با اندازه ی ۵ گلوگاهی هستش. (اون جور که من از سوال برداشت میکنم.)
ولی در درخت فراگیر نه کمینه هستش و نه بیشینه. ضمناً همون طور که ملاحظه میشه کوچکترین یال هم نیست.
پس گزینه ی چهار میمونه که اونم باز نمیشه. چون اگه همه ی یالها با هم برابر باشند، عددگلوگاهی میتونه برابر بیشترین وزن یالها باشه.
خلاصه اینکه طراح، نا مردی کرده...
دوست عزیز شما داری سوال رو اشتباه میخونی.درخت فراگیر کمینه یعنی MST .ولی شما برداشت کردید که اندازه باید کمینه باشه.( درختِ فراگیرِ کمینه) باید خونده بشه!
عِه ؟!!!!!!!!!!!!
یعنی واقعاً باید ( درختِ فراگیرِ کمینه)خونده بشه؟!
عجب!
ولی باز هم اگه اون گرافی رو که گذاشتم در نظر بگیرید، هم گزینه ی ۳ و هم ۲ درست میشه. یعنی هم توی درختِ فراگیرِ کمینه هست و هم توی بیشینه.
البته من برای اولین بار بود که اصطلاح گلوگاهی رو میشنیدم و خودم پیش خودم دقیقاً همین گرافی رو که گذاشتم روی کاغذ کشیدم و یکی یکی حالت ها رو بررسی کردم.
بنظرم اصلا سوال غلطه. چه برداشتِ من درست باشه، چه برداشت شما، باز هم گزینه ها درست نیستند. اون یالِ با وزنِ ۵ در تمام درخت های فراگیر حضور داره!
البته این احتمال هم هست که من درست سوال رو متوجه نشده باشم. مثل اینکه دوستان میگند قبلاً نکتش رو خونده بودند. ولی اگه میشه روی همین گرافی که گذاشتم بررسی کنید ببینید باز هم نظرتون درسته یا نه.
