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