درخت پوشا

در رشتهٔ ریاضیات و در زیرشاخهٔ نظریه گراف، یک ‍‍‍‍‍‍‍‍‍‍درخت پوشا T، از گراف همبند و بدون جهت G درختی است که شامل تمام رئوس و حداقل برخی یال‌ها می‌باشد. به بیان ساده‌تر می‌توان گفت، درخت پوشای G درختی است که مجموعه‌ای از یال‌ها را شامل می‌شود در حالی که تمام رئوس را پوشش می‌دهد. در واقع تمام رئوس G در درخت پوشا وجود دارند به شرطی که هیچ دوری ایجاد نشود و درخت همبند نیز باشد.

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

درخت پوشای گراف همبند G را می‌توان این‌گونه نیز تعریف کرد:

• مجموعه‌ای حداکثری از یال‌های G که هیچ دوری در آن وجود ندارد، و یا
• مجموعه‌ای حداقلی از یال‌های G که همهٔ رئوس را به یکدیگر متصل می‌کند.

در برخی از زیر رشته‌های نظریهٔ گراف‌ها معمولاً پیدا کردن درخت پوشای کمینه در یک درخت وزن دار مورد بررسی قرار می‌گیرد.

مسائل بهینه سازی دیگری نیز در مورد درخت‌های پوشا بررسی شده‌اند ازجمله موارد زیر

• درخت پوشای بیشینه
• درخت کمینه‌ای که شامل حداقل k رأس باشد
• درخت پوشای کمینه‌ای که حداکثر k یال به ازای هر رأس دارد
• درخت پوشایی که بیشترین تعداد برگ را دارد
• درخت پوشایی با کم‌ترین تعداد برگ (مربوط می‌شود به مسئلهٔ مسیر همیلتونی)
• درخت پوشایی با کم‌ترین قطر

کاربردها

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

تعریف

اگر گراف همبند باشد (یعنی از هر نقطه بتوان به یک نقطه دلخواه دیگر رسید) ولی دور نداشته باشد (یعنی هیچ نقطه‌ای از دوراه به نقطهٔ بعدی نرسد) می‌گویند گراف درختی است. درخت و ماتریس درخت در رشته‌های مختلفی مانند شیمی مهندسی برق و علم محاسبه کاربرد دارد. کیرشهف در سال ۱۸۴۷ میلادی هنگام حل دستگاههای معادلات خطی مربوط به شبکه‌های الکتریکی درختها را کشف و نظریه درختها را بارور کرد. کیلی در سال ۱۸۵۷ میلادی درختها را در ارتباط با شمارش ایزومرهای مختلف هیدروکربنها کشف کرد.

دورهای اساسی

اضافه نمودن حتی یک یال به درخت پوشا باعث ایجاد دور می‌شود، چنین دوری را یک دور اساسی نامیده‌اند. برای هر یالی، دور اساسی مجزایی وجود دارد. بنابراین می‌توان گفت یک ارتباط یک به یک بین دورهای اساسی و یال‌هایی که در درخت پوشا شرکت نمی‌کنند وجود دارد. برای درخت همبندی با V تا رأس، هر درخت پوشایی V-1 یال خواهد داشت، در نتیجه هر گرافی با E یال، E-V-1 دور اساسی خواهد داشت. برای هر درخت پوشای داده شده این دورها، پایه‌ای برای فضای دوری تشکیل می‌دهند.

مفهوم دور اساسی مفهومی دوگان به نام مجموعه برش اساسی دارد. با حذف هر یک از یال‌ها در درخت پوشا، رئوس به دو دستهٔ مجزا تقسیم می‌شوند. مجموعه برش اساسی این‌گونه تعریف شده‌است: مجموعهٔ یال‌هایی که باید از گراف جدا شوند تا به تقسیم مشابهی برسیم. در نتیجه به طور دقیق V-1 مجموعه برش اساسی وجود دارد، هر یک برای یکی از یال‌های درخت پوشا. دوگان بین دو مفهوم دور اساسی و مجموعه برش اساسی از آنجا ایجاد شد که، یال‌های ایجاد کننده دور که در درخت پوشا نیستند، فقط می‌توانند در مجموعه برش‌هایی از دیگر رئوس در دور حاضر شوند؛ و بر عکس: یال‌های موجود در مجموعه برش فقط می‌توانند در دورهایی ظاهر شوند که شامل یال مربوط به مجموعه برش هستند.

جنگل‌های پوشا

جنگل پوشا، نوعی زیر درخت می‌باشد که مفهوم درخت پوشا را تعمیم داده‌است. دو تعریف متداول برای آن وجود دارد: جنگل پوشا زیر درختی است که شامل درخت پوشا در هر یک از بخش‌های همبند آن می‌باشد. به عبارت دیگر، زیر درخت بیشینه‌ای است که دور ندارد. این تعریف بیشتر در علوم کامپیوتر و بهینه سازی کاربرد دارد. تعریف دیگر که در نظریهٔ گراف‌ها کاربرد دارد، این‌گونه‌است: جنگل پوشا هر زیر درختی است که هم جنگل است (یعنی دور ندارد) و هم پوشا (یعنی شامل تمام رئوس می‌شود).

شمارش درخت‌های پوشا

عدد t(G) که تعداد درخت‌های پوشای درخت G می‌باشد، ثابت مهمی است. در برخی موارد به راحتی محاسبه می‌شود و به دست می‌آید و به صورت گسترده در داده ساختارهای مختلف در زبان‌های رایانه‌ای گوناگون کاربرد دارد. برای مثال، اگر G خودش یک درخت باشد، t(G) =1 خواهد بود؛ و اگر G یک گراف دوری با n رأس باشد، t(G) = n خواهد بود. برای هر گرافی مقدار ثابت t(G) از نظریهٔ ماتریس-درخت کیرچوف قابل محاسبه می‌باشد. فرمول کایلِی فرمولی برای محاسبهٔ t(G) در درخت‌های کامل ($K_{n}$ درخت کامل با n رأس) می‌باشد. این فرمول نشان می‌دهد که $t(K_{n})=n^{n-2}$. اگر G گراف کامل دو بخشی ($K_{p,q}$) باشد خواهیم داشت: $t(G)=p^{q-1}q^{p-1}$.
فرمول کایلِی به وسیلهٔ نظریهٔ ماتریس-درخت کیرچوف یا کدِ پوفر قابل اثبات می‌باشد.

درخت‌های پوشای یکسان

درخت پوشایی که به طور تصادفی از بین همهٔ درخت‌های پوشای با احتمال برابر انتخاب شود را درخت پوشای یکسان می‌نامند. این مدل به طور گسترده در احتمالات و ریاضی فیزیک تحقیق و بررسی می‌شود.

الگوریتم‌های ارائه شده برای درخت پوشا

الگوریتم سنتی و متداول درخت پوشا بر مبنای جستجوی اول عمق (DFS) و جستجوی اول سطح (BFS) کار می‌کنند. الگوریتم‌های موازی از روش‌ها و رهیافت‌های دیگری به جز DFS و BFS استفاده می‌کنند. هالپرین و زوییک الگوریتم موازی تصادفی بهینه‌ای که زمان اجرایش O(log n) می‌باشد بر روی EREW PRAM طراحی کرده‌اند. الگوریتم شیلوچ-ویشکین که بر اساس تحقیقات یوسی شیلوچ و یوزی ویشکین طراحی شده‌است، پایه و اساس بسیاری از پیاده سازی‌های موازی می‌باشد. الگوریتم بادر و کونگ نشان داده‌است که در گراف‌های گوناگون، بسیار سریع کار می‌کند.
معمول‌ترین الگوریتم توزیع شده پروتکل درخت پوشا می‌باشد که توسط دستگاه‌های لایهٔ لینک در مدلOSI از شبکه‌های رایانه‌ای استفاده می‌شود. این دستگاه‌ها که عمدتاً روترها و سوئیچ‌ها هستند برای جلوگیری از توفان انتشار پیام‌های مسیریابی در شبکه‌های رایانه‌ای مورد استفاده قرار می‌گیرند. در واقع در هر مرحله دور موجود در شبکه را با غیر فعال کردن برخی از یال‌ها از بین می‌برند تا پیام‌های انتشاری در حلقه گیر نکنند و در شبکه اکو نشوند.

جستارهای وابسته

• درخت فراگیر مینیمم
• الگوریتم دیکسترا
• پروتکل درخت پوشا
• الگوریتم ادمون
• الگوریتم پریم
• الگوریتم کروسکال