درخت پوشا
From Wikipedia, the free encyclopedia
در رشتهٔ ریاضیات و در زیرشاخهٔ نظریه گراف، یک درخت پوشا T، از گراف همبند و بدون جهت G درختی است که شامل تمام رئوس و حداقل برخی یالها میباشد. به بیان سادهتر میتوان گفت، درخت پوشای G درختی است که مجموعهای از یالها را شامل میشود در حالی که تمام رئوس را پوشش میدهد. در واقع تمام رئوس G در درخت پوشا وجود دارند به شرطی که هیچ دوری ایجاد نشود و درخت همبند نیز باشد.
درخت پوشای گراف همبند G را میتوان اینگونه نیز تعریف کرد:
- مجموعهای حداکثری از یالهای G که هیچ دوری در آن وجود ندارد، و یا
- مجموعهای حداقلی از یالهای G که همهٔ رئوس را به یکدیگر متصل میکند.
در برخی از زیر رشتههای نظریهٔ گرافها معمولاً پیدا کردن درخت پوشای کمینه در یک درخت وزن دار مورد بررسی قرار میگیرد.
مسائل بهینه سازی دیگری نیز در مورد درختهای پوشا بررسی شدهاند ازجمله موارد زیر
- درخت پوشای بیشینه
- درخت کمینهای که شامل حداقل k رأس باشد
- درخت پوشای کمینهای که حداکثر k یال به ازای هر رأس دارد
- درخت پوشایی که بیشترین تعداد برگ را دارد
- درخت پوشایی با کمترین تعداد برگ (مربوط میشود به مسئلهٔ مسیر همیلتونی)
- درخت پوشایی با کمترین قطر