تخفیف ویژه زمستانه پی استور
تا 60 درصد تخفیف
شامل پروژه‌ها و دوره‌های آموزشی
روز
ساعت
دقیقه
ثانیه
تخفیف ویژه زمستانه پی استور
در واقع تمام رئوس G در درخت پوشا وجود دارند به شرطی که هیچ حلقه یا دوری ایجاد نشود و درخت همبند نیز باشد. درخت پوشای کمینه (Minimum Spanning Tree) یک درخت پوشا است که داری کمترین هزینه (مجموع هزینه یال‌ها) باشد. مثال زیر را در نظر بگیرید.
در گراف G سمت چپ یک گراف وزن دار همبند غیر جهت است. دو گراف دیگر زیر مجموعه‌ای از گراف G هستند که در شامل تمام راس‌ها می‌باشد و دوری در آن تشکیل نشده است. درختT اول دارای هزینه ۱۱ و درخت دوم دارای هزینه ۷ می‌باشد پس هر دو درخت، درخت پوشا هستند ولی درخت دوم به دلیل هزینه کمتر درخت پوشای کمینه است.
درخت پوشای مینیمم یا درخت فراگیر مینیمم در گراف‌های وزن دار ساخته می‌شود. فرض کنید گراف، یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد). منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال‌های آن‌را در برگیرد. منظور از درخت پوشای مینیمم (برای گراف همبند وزن دار) درختی است که بین درخت‌های پوشای آن گراف، مجموع وزن یال‌های آن، کمترین مقدار ممکن باشد.
برای به دست آوردن درخت پوشای بهینه یک گراف جهت دار متصل می‌توان از الگوریتم‌های متفاوتی استفاده نمود. سه الگوریتم معروف برای پیدا کردن درخت پوشای کمینه عبارتند از : الگوریتم کروسکال، الگوریتم پریم و الگوریتم سولین.
الگوریتم‌های دیگری نیز برای حل مسئله پیدا کردن درخت پوشای مینیمم ارائه شده‌اند که با رویکرد تکاملی مسئله را حل می‌کنند از جمله مهمترین آنها می‌توان به الگوریتم ژنتیک، PSO، رقابت استعماری و کرم شب تاب اشاره کرد.
برای مثال فرض کنید در شهری می‌خواهیم طوری شبکه ایجاد کنیم که بتوان از هر گره به هر گره دیگری مسیر وجود داشته باشد و هزینه کابل کشی بین هر دو گره را داریم. برای پیدا کردن کم هزینه‌ترین شبکه بندی، باید درخت پوشای کمینه را بیابیم.
در این پست درباره درخت پوشای مینیمم و موارد مهم مربوط به آن اطلاعاتی خدمت شما عزیزان ارائه کرده‌ایم. الگوریتم‌های مختلفی برای پیدا کردن درخت پوشای مینیمم همچون کروسکال، پریم،سولین وجود دارد که درپست حاضر ذکر گریده اند. همچنین الگوریتم‌هایی که از طریق حل مسئله در روند پیدا کردن درخت پوشای به کار گرفته می‌شوند مانند الگوریتم‌های ژنتیک، رقابت استعماری، کرم شب تاب و غیره نیز بیان گردیده اند. کاربردهای درخت پوشای مینیمم از دیگر مواردی است که در پست کنونی توضیح داده شده است.
