سلام میشه بگین چرا گزینه ۴ نمیشه
خوب احتمال داره بزرگترین یال گراف توی MST باشه
که اگه حذفش کنیم مجبور شیم از یه مسیر دیگه ای بریم که نسبت به قبل بهینه نیست و مجموع وزنهاش بیشتر بشه!
(۱۰ بهمن ۱۳۹۳ ۰۸:۲۲ ب.ظ)tm.viper نوشته شده توسط: سلام میشه بگین چرا گزینه ۴ نمیشهبزرگترین یال یک دور نه گراف .. بزرگترین یال یک دور حتما توی MST نیست
خوب احتمال داره بزرگترین یال گراف توی MST باشه
که اگه حذفش کنیم مجبور شیم از یه مسیر دیگه ای بریم که نسبت به قبل بهینه نیست و مجموع وزنهاش بیشتر بشه!
سلام
به نظرم ۱ و ۴ هردو درستند.
نقل قول: بزرگترین یال یک دور نه گراف .. بزرگترین یال یک دور حتما توی MST نیستبه راحتی میشه برای این ادعا مثال نقض آورد.
بابا این مدرسان واقعا طراحای بدرد نخوری داره
هر سری میام خونه مشکل دارم با این جواباش
دوست عزیز اگر میشه مثال نقض بیار
به نظر من که گزینه های ۲ و ۳ درسته
و همون حرف دوستمون رو قبول دارم که یال بزرگتر داخل دور، اصلا تو MST نیست
(۱۰ بهمن ۱۳۹۳ ۰۹:۴۳ ب.ظ)MShariati نوشته شده توسط: سلام
به نظرم ۱ و ۴ هردو درستند.
نقل قول: بزرگترین یال یک دور نه گراف .. بزرگترین یال یک دور حتما توی MST نیستبه راحتی میشه برای این ادعا مثال نقض آورد.
مثال نقضتون چیه؟
(۱۰ بهمن ۱۳۹۳ ۱۰:۲۳ ب.ظ)L3ic نوشته شده توسط: به نظر من که گزینه های ۲ و ۳ درستهمنم با نظر شما موافقم
و همون حرف دوستمون رو قبول دارم که یال بزرگتر داخل دور، اصلا تو MST نیست
(۱۰ بهمن ۱۳۹۳ ۰۹:۴۳ ب.ظ)MShariati نوشته شده توسط: سلام
به نظرم ۱ و ۴ هردو درستند.
نقل قول: بزرگترین یال یک دور نه گراف .. بزرگترین یال یک دور حتما توی MST نیستبه راحتی میشه برای این ادعا مثال نقض آورد.
مثال نقضتون چیه؟
سلام
مثال نقض:
[attachment=17946]
تور بهینه محیط این شکل می باشد. همچنین توجه کنید که با حذف یال (۰و۲) درستی گزینه ۴ هم محرز میشود.
نکتهی تستی:
هر وقت خواستید به چنین سؤالی جواب بدید ولی خیلی بهش مسلط نیستید و یا وقت برای حلش ندارید،
گزینههای محدودتر به احتمال قویتری غلط میباشند.
گزینههای ۲ و ۳ با داشتن عبارت "برابر" بسیار محدود و دقیق هستند، حال آنکه گزینههای ۱ و ۴ با داشتن عبارات "ممکن است" و "بیشتر" بسیار ریلکستر هستند.
(۱۱ بهمن ۱۳۹۳ ۰۸:۲۲ ق.ظ)MShariati نوشته شده توسط: سلام
مثال نقض:
تور بهینه محیط این شکل می باشد. همچنین توجه کنید که با حذف یال (۰و۲) درستی گزینه ۴ هم محرز میشود.
نکتهی تستی:
هر وقت خواستید به چنین سؤالی جواب بدید ولی خیلی بهش مسلط نیستید و یا وقت برای حلش ندارید،
گزینههای محدودتر به احتمال قویتری غلط میباشند.
گزینههای ۲ و ۳ با داشتن عبارت "برابر" بسیار محدود و دقیق هستند، حال آنکه گزینههای ۱ و ۴ با داشتن عبارات "ممکن است" و "بیشتر" بسیار ریلکستر هستند.
دوست عزیز از کی تا الان ۲ از ۳ بزرگتر شدّه
سنگین ترین یال دور نه سبک ترین ... سنگین ترین تو مثال شما ۳ هست نه ۲ ... مثالتون اشتباهه واضحا .. در ضمن والله ۹۰% درصد مطمئنم که گزاره ای که گفتم (سنگین ترین یال دور در هیچ MST نیست ) رو توی CLRS دیده بودم
(۱۱ بهمن ۱۳۹۳ ۰۹:۵۹ ق.ظ)Densike نوشته شده توسط:(11 بهمن ۱۳۹۳ ۰۸:۲۲ ق.ظ)MShariati نوشته شده توسط: سلام
مثال نقض:
تور بهینه محیط این شکل می باشد. همچنین توجه کنید که با حذف یال (۰و۲) درستی گزینه ۴ هم محرز میشود.
نکتهی تستی:
هر وقت خواستید به چنین سؤالی جواب بدید ولی خیلی بهش مسلط نیستید و یا وقت برای حلش ندارید،
گزینههای محدودتر به احتمال قویتری غلط میباشند.
گزینههای ۲ و ۳ با داشتن عبارت "برابر" بسیار محدود و دقیق هستند، حال آنکه گزینههای ۱ و ۴ با داشتن عبارات "ممکن است" و "بیشتر" بسیار ریلکستر هستند.
دوست عزیز از کی تا الان ۲ از ۳ بزرگتر شدّه
سنگین ترین یال دور نه سبک ترین ... سنگین ترین تو مثال شما ۳ هست نه ۲ ... مثالتون اشتباهه واضحا .. در ضمن والله ۹۰% درصد مطمئنم که گزاره ای که گفتم (سنگین ترین یال دور در هیچ MST نیست ) رو توی CLRS دیده بودم
چقدر عجولانه جواب میدید! بیشتر دقت کنید، فکر نمیکنم نیازی به توضیح بیشتر باشه.
من اشتباه کردم ، یال ۰ به ۲ رو شما حذف کردید
ولی باز هم حرف شما اشتباه هست
یال ۰ ۲ توی هیچ MST نیست همونطوری که گفتم هزینه MST در هر ۲ صورت چه این یال باشه چه نباشه ۶ هست
(۱۱ بهمن ۱۳۹۳ ۰۲:۱۳ ب.ظ)Densike نوشته شده توسط: من اشتباه کردم ، یال ۰ به ۲ رو شما حذف کردید
ولی باز هم حرف شما اشتباه هست
یال ۰ ۲ توی هیچ MST نیست همونطوری که گفتم هزینه MST در هر ۲ صورت چه این یال باشه چه نباشه ۶ هست
عذر میخواهم؛ یک اشتباه اساسی کردم!
من از اول به اشتباه TSP رو به جای MST در نظر گرفته بودم.
ادعای فوق برای MST صد درصد درسته و همون ۲ و ۳ جوابه.