درخت پوشا (Spanning Tree)، در ریاضیات (Mathematics)

انواع درخت (Tree) را در آموزش زیر شرح دادیم :

درخت پوشا (Spanning Tree) :

اگر گراف همبند G داشته باشیم، یک درخت پوشا زیرگرافی از G است که یک درخت بوده و تمام رئوس G را شامل می شود. به عبارت دیگر، مجموعه ای از یال های گراف اصلی است که کمترین تعداد یال ممکن برای حفظ اتصال بین تمام رئوس را نگه می دارد. تعداد یال های آن برابر با

است. گراف ها می توانند درخت های پوشای متعددی داشته باشند. اگر به یال ها وزن (Weight) نسبت داده شود، درخت پوشای کمینه (Minimum Spanning Tree - MST) درختی است که مجموع وزن یال های آن کمترین مقدار ممکن باشد. الگوریتم های کراسکال (Kruskal) و پریم (Prim) برای یافتن MST استفاده می شوند.