هزاره سوم
جمعه 03 خرداد 1392, 09:50 صبح
سلام دوستان
کسی میتونه این 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 را بجای آن دو رسم کند (مانند شکل چپ). با تکرار این عمل تا جای ممکن، دست کم چه تعداد تکه خط ممکن است باقی بماند؟ (دقت کنید که در شکل سمت راست هیچ سه نقطه ای در یک خط نیستند)