درخت پوشای کمینه در گراف‌هایی تعریف می‌شود که یال‌های گراف وزن(ارزش) داشته باشند. به اصلاح در گراف‌های وزن‌دار تعریف می‌شود. زیر مجموعه از یالهای گراف که یک درخت شامل تمام راس‌ها تشکیل می‌دهد و مجوع وزن یال‌هایشان کمترین مقدار ممکن بین تمام چنین درخت‌هایی باشد، درخت پوشای کمینه می‌گویند. در واقع مسئله پیدا کردن یک زیر مجموعه‌ از یال‌های گراف با کم‌ترین مجموع وزن است که بین هر دو راس این زیر گراف همچنان مسیر وجود داشته باشد.

نمونه‌ای از الگوریتم‌ها برای پیدا کردن درخت پوشای کمینه، الگوریتم پریم و الگوریتم کروسکال است.

امکان وجود بیش از یک درخت پوشای کمینه وجود دارد، برای مثال اگر تمام یال‌ها وزن برابری داشته باشند، تمام زیر در خت ها درخت پوشای کمینه هستند. اگر وزن هر دو یال با هم متفاوت باشد، تنها یک درخت پوشای کمینه خواهیم داشت. اثبات این ویژگی، همان اثبات الگوریتم کروسکال است. زیرا در چنین گرافی، این الگوریتم یک درخت واحد تولید می‌کند.

ادعا: اگر گراف را به دو مجموعه $V$ و $V'$ از راس‌ها افراز کنیم، کم‌وزن ترین یال بین یال‌هایی که یک طرفشان در مجموعه $V$ و طرف دیگرشان در مجموعه $V'$ است باید جزء درخت پوشای کمینه باشد. (اگر چند یال با کم‌ترین وزن وجود داشت، باید دقیقا یکی از آنها جزء درخت پوشای کمینه باشد). اثبات این ویژگی را می‌توانید در بررسی صحت الگوریتم پریم بخوانید.

اگر کم‌وزن‌ترین یال گراف یکتا باشد در هر درخت پوشای کمینه‌ای وجود خواهد داشت. اثبات این ویژگی همان اثبات الگوریتم کروسکال است.

اگر یالی در یک دور از تمام یال‌های موجود در آن دور وزنش بیش‌تر باشد، نمی‌تواند در درخت پوشای کمینه قرار بگیرد. فرض خلف: فرض کنید این یال در یک درخت پوشای کمینه وجود دارد، اگر آنرا حذف کنیم درخت به دو مولف تقسیم می‌شود و دور مذکور در گراف اصلی بدون این یال یک مسیر بین این دو مولفه می‌شود. یالی از این مسیر که این مسیر را از این مولفه به آن مولفه منتقل می‌کند جایگزین یال حذف شده به درخت اضافه کنید(ممکن است چند یال این کار را بکنند که مهم نیست کدام را انتخاب می‌کنیم). این یال کم‌وزن‌تر است پس مجموع وزن‌های یال‌های درخت جدید کم‌تر است که با کمینه بودن درخت اول در تناقض است.

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

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