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

 

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

 

== الگوریتم کروسکال ==

{{پانویس}}

{{چپ‌چین}}

{{پایان چپ‌چین}}

{{الگوریتم‌های بهینه‌سازی}}

[[رده:درخت پوشا]]