درخت پوشای کمینه: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
جز ربات:حذف تصویر ناموجود |
جز ربات: اصلاح ترکیبی |
||
خط ۱:
'''درخت پوشای بهینه''' در [[گراف|گرافهای]] ارزش دار (وزن دار) ساخته میشود.
فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال های آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گرف همبند وزن دار) درختی است که بین درخت های پوشای آن گراف، مجموع وزن یال های آن، کمترین مقدار ممکن باشد.
[[الگوریتم کراسکال]]
[[الگوریتم پریم]]
|