تفاوت میان نسخه‌های «درخت پوشای کمینه»

هیچ تغییری در اندازه به وجود نیامده‌ است. ،  ۹ سال پیش
جز
ربات: اصلاح ترکیبی
جز (ربات:حذف تصویر ناموجود)
جز (ربات: اصلاح ترکیبی)
'''درخت پوشای بهینه''' در [[گراف|گراف‌های]] ارزش دار (وزن دار) ساخته می‌شود.
 
فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال های آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گرف همبند وزن دار) درختی است که بین درخت های پوشای آن گراف، مجموع وزن یال های آن، کمترین مقدار ممکن باشد.برايبرای به دست آوردن درخت پوشايپوشای بهینه يکیک گراف جهت دار متصل ميمی توان از الگوريتمالگوریتم های متفاوتی استفاده نمود.البته بطور کلی دو الگوریتم برای درخت پوشای مینیمم وجود دارد که عبارتند از :
[[الگوریتم کراسکال]]
[[الگوریتم پریم]]
۱۶۴٬۵۲۷

ویرایش