درخت پوشا

در رشتهٔ ریاضیات و در زیرشاخهٔ نظریه گراف، یک ‍‍‍‍‍‍‍‍‍‍درخت پوشا T، از گراف همبند و بدون جهت G درختی است که شامل تمام رئوس و حداقل برخی یال ها می باشد. به بیان ساده تر می توان گفت، درخت پوشای G درختی است که مجموعه ای از یال ها را شامل می شود در حالی که تمام رئوس را پوشش می دهد. در واقع تمام رئوس G در درخت پوشا وجود دارند به شرطی که هیچ دوری ایجاد نشود و درخت همبند نیز باشد.
درخت پوشای گراف همبند G را می توان این گونه نیز تعریف کرد:
• مجموعه ای حداکثری از یال های G که هیچ دوری در آن وجود ندارد، و یا
• مجموعه ای حداقلی از یال های G که همهٔ رئوس را به یکدیگر متصل می کند.
در برخی از زیر رشته های نظریهٔ گراف ها معمولاً پیدا کردن درخت پوشای کمینه در یک درخت وزن دار مورد بررسی قرار می گیرد.
مسائل بهینه سازی دیگری نیز در مورد درخت های پوشا بررسی شده اند ازجمله موارد زیر
• درخت پوشای بیشینه
• درخت کمینه ای که شامل حداقل k رأس باشد
• درخت پوشای کمینه ای که حداکثر k یال به ازای هر رأس دارد
• درخت پوشایی که بیشترین تعداد برگ را دارد
• درخت پوشایی با کم ترین تعداد برگ ( مربوط می شود به مسئلهٔ مسیر همیلتونی )
• درخت پوشایی با کم ترین قطر
بعضی الگوریتم های مسیریابی از درخت پوشا یک قدم مهم برای حل مسئله می سازند. به عنوان نمونه برای کاهش هزینه های شبکه های نیرو ، اتصالات سیمی ، لوله کشی ها و. . . سعی می کنند شبکه ی مدنظر را به یک درخت پوشا تبدیل کنند.
اگر گراف همبند باشد ( یعنی از هر نقطه بتوان به یک نقطه دلخواه دیگر رسید ) ولی دور نداشته باشد ( یعنی هیچ نقطه ای از دوراه به نقطهٔ بعدی نرسد ) می گویند گراف درختی است. درخت و ماتریس درخت در رشته های مختلفی مانند شیمی مهندسی برق و علم محاسبه کاربرد دارد. کیرشهف در سال ۱۸۴۷ میلادی هنگام حل دستگاههای معادلات خطی مربوط به شبکه های الکتریکی درختها را کشف و نظریه درختها را بارور کرد. کیلی در سال ۱۸۵۷ میلادی درختها را در ارتباط با شمارش ایزومرهای مختلف هیدروکربنها کشف کرد.
اضافه نمودن حتی یک یال به درخت پوشا باعث ایجاد دور می شود، چنین دوری را یک دور اساسی نامیده اند. برای هر یالی، دور اساسی مجزایی وجود دارد. بنابراین می توان گفت یک ارتباط یک به یک بین دورهای اساسی و یال هایی که در درخت پوشا شرکت نمی کنند وجود دارد. برای درخت همبندی با V تا رأس، هر درخت پوشایی V - 1 یال خواهد داشت، در نتیجه هر گرافی با E یال، E - V - 1 دور اساسی خواهد داشت. برای هر درخت پوشای داده شده این دورها، پایه ای برای فضای دوری تشکیل می دهند.