الگوریتم کروسکال و درخت پوشای کمینه
سلام دوستان
کسی میتونه این 2تا سوال رو حل کنه؟
:(
خیلی به کمک احتیاج دارم
سوال :
1- نشان دهید اگر G یک گراف همبند باشد و وزن همه یال ها متمایز باشد آنگاه درخت پوشای مینیمم منحصر به فرد است، اما دومین بهترین درخت پوشای مینیمم لزوماً منحصر به فرد نیست؟
2-پویا سمت راست شکل زیر را رسم کرده و به شاندیز داده است. این شکل از ۱۲ دایره سیاه و ۱۸ تکه خط (پاره خطی که دو سر آن دایره سیاه وجود دارد) تشکیل شده است. http://upload.tehran98.com/img1/0ok0tsytlmfaoojx2zd.jpg
شاندیز در هر مرحله می تواند سه دایره سیاه A، B و C را که A به B و A به C با تکه خط متصل اند ولی B به C متصل نیست انتخاب کند و تکه خط AB و AC را حذف و تکه خط BC را بجای آن دو رسم کند (مانند شکل چپ). با تکرار این عمل تا جای ممکن، دست کم چه تعداد تکه خط ممکن است باقی بماند؟ (دقت کنید که در شکل سمت راست هیچ سه نقطه ای در یک خط نیستند)
نقل قول: الگوریتم کروسکال و درخت پوشای کمینه
یعنی هیچکی نمیتونه کمکم کنه؟!!!!
:(
نقل قول: الگوریتم کروسکال و درخت پوشای کمینه
کسی هست مرا یاری کند؟
:ناراحت:
نقل قول: الگوریتم کروسکال و درخت پوشای کمینه
چرا هیچکــــــــی جواب سوال منو نمیدهــــــــــه
:افسرده::متفکر::عصبانی:
نقل قول: الگوریتم کروسکال و درخت پوشای کمینه
نقل قول:
نوشته شده توسط
هزاره سوم
سلام دوستان
کسی میتونه این 2تا سوال رو حل کنه؟
:(
خیلی به کمک احتیاج دارم
سوال :
1- نشان دهید اگر G یک گراف همبند باشد و وزن همه یال ها متمایز باشد آنگاه درخت پوشای مینیمم منحصر به فرد است، اما دومین بهترین درخت پوشای مینیمم لزوماً منحصر به فرد نیست؟
2-پویا سمت راست شکل زیر را رسم کرده و به شاندیز داده است. این شکل از ۱۲ دایره سیاه و ۱۸ تکه خط (پاره خطی که دو سر آن دایره سیاه وجود دارد) تشکیل شده است.
http://upload.tehran98.com/img1/0ok0tsytlmfaoojx2zd.jpg
شاندیز در هر مرحله می تواند سه دایره سیاه A، B و C را که A به B و A به C با تکه خط متصل اند ولی B به C متصل نیست انتخاب کند و تکه خط AB و AC را حذف و تکه خط BC را بجای آن دو رسم کند (مانند شکل چپ). با تکرار این عمل تا جای ممکن، دست کم چه تعداد تکه خط ممکن است باقی بماند؟ (دقت کنید که در شکل سمت راست هیچ سه نقطه ای در یک خط نیستند)
سلام
اگه جواب سوالها رو پیداکردی در ادامه بگو!