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

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

ویرایش