درخت پوشای مینیمم 

درخت پوشای مینیمم یا درخت پوشای کمینه

در نظریه گراف، درخت پوشا T، درختی است از یک گراف G کامل و بدون جهت و وزن دار که شامل تمام راس ها و حداقل یال‌ها می‌باشد. به بیان دیگر می‌توان گفت، درخت پوشای G درختی است که مجموعه‌ای از یال‌ها را شامل می‌شود  که تمام رئوس را پوشش می‌دهد. در واقع تمام رئوس G در درخت پوشا وجود دارند به شرطی که هیچ حلقه یا دوری ایجاد نشود و درخت همبند نیز باشد. درخت پوشای کمینه (Minimum Spanning Tree) یک درخت پوشا است که داری کمترین هزینه (مجموع هزینه یال ها) باشد. مثال زیر را در نظر بگیرید.

در گراف G سمت چپ یک گراف وزن دار همبند غیر جهت است. دو گراف دیگر زیر مجموعه ای از گراف G هستند که در شامل تمام راس ها می باشد و دوری در آن تشکیل نشده است. درختT اول دارای هزینه 11 و درخت دوم دارای هزینه 7 می باشد پس هر دو درخت، درخت پوشا هستند ولی درخت دوم به دلیل هزینه کمتر درخت پوشای کمینه است.

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

الگوریتم های دیگری نیز برای حل مسئله پیدا کردن درخت پوشای مینیمم ارائه شده اند که با رویکرد تکاملی مسئله را حل می کنند از جمله مهمترین آنها می توان به الگوریتم ژنتیک، PSO، رقابت استعماری و کرم شب تاب اشاره کرد.

کاربرد های درخت پوشای مینیمم

در مسائلی که هدف ایجاد شبکه‌ای است که برای ایجاد ارتباط بین هر دو عضو آن هزینه‌ای باید بپردازیم و می‌خواهیم در نهایت در این شبکه بین هر دو عضو ارتباط وجود داشته باشد، درخت پوشای کمینه همان کم هزینه‌ترین شبکه است. برای مثال فرض کنید در شهری می‌خواهیم طوری شبکه ایجاد کنیم که بتوان از هر گره به هر گره دیگری مسیر وجود داشته باشد و هزینه کابل کشی بین هر دو گره را داریم. برای پیدا کردن کم هزینه‌ترین شبکه بندی، باید درخت پوشای کمینه را بیابیم.