درخت پوشای کمینه (Minimum Spanning Tree - MST)، در ریاضیات (Mathematics)

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

درخت پوشای کمینه (Minimum Spanning Tree - MST) :

این مفهوم دقیقا مشابه درخت پوشا (Spanning Tree) است، اما با تأکید بر بهینه سازی وزن. در مسائل شبکه های ارتباطی، طراحی مدارهای چاپی و خوشه بندی داده ها کاربرد دارد. فرض کنید می خواهیم با کمترین هزینه کابل کشی، تمام شهرها را به شبکه برق متصل کنیم. MST جواب این مسئله است. یک ویژگی مهم MST این است که برای هر برش (Cut) از گراف، یال با کمترین وزن که آن برش را قطع می کند، حتما در MST قرار دارد. این ویژگی مبنای کار الگوریتم های حریصانه (Greedy) برای ساخت MST است.