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