Tree Covering

در واقع مسئله می‌خواهد که ما رئوس گراف را به چند مجموعه افراز کنیم که:

    
-     ا ندازه‌ی هر مجموعه حداکثر $s$ باشد.
-        برای هر مجموعه، رأسی در درخت (که ممکن است از خود آن مجموعه هم نباشد) وجود داشته باشد که فاصله‌اش با همه‌ی رئوس آن مجموعه حداکثر $k$ باشد. این رأس درواقع جایی است که مهره‌ی متناظر با این مجموعه را در آن قرار می‌دهیم.
 

در ابتدا مسئله را در حالتی که فقط شرط دوم وجود دارد حل می‌کنیم. سپس الگوریتمی برای حل مسئله‌ی اصلی ارائه می‌دهیم.

در حالتی که فقط شرط دوم وجود داشته باشد با یک بار DFS و به روش حریصانه مسئله را حل می‌کنیم. به این شکل که در هنگام اجرای DFS ، فرض کنید به رأسی مثل $v$ رسیدیم. پس از صدا زدن DFS همه‌ی بچه‌های $v$، اگر دورترین نوه‌ای از $v$ که هنوز توسط هیچ مهره‌ای پوشانده نشده است، فاصله‌ای به اندازه‌ی $k$ با رأس $v$ داشته باشد، در آن صورت روی رأس $v$ یک مهره می‌گذاریم. برای اینکه بتوانیم دورترین نوه‌ی $v$ را محاسبه کنیم، تابع $v$ را به شکلی پیاده‌سازی می‌کنیم که به عنوان خروجی فاصله‌ی دورتین رأس پوشانده نشده را برگرداند. در این صورت با ماکسیمم گرفتن این مقدار بین همه‌ی بچه‌های $v$ می‌توانیم فاصله‌ی دورترین نوه‌ی $v$ که هنوز توسط هیج رأسی پوشانده نشده است را به‌دست آوریم. نکته‌ی دیگر این است که وقتی مهره‌ای در رأس $v$ می‌گذاریم، این مهره می‌تواند نه تنها نوادگان خود، بلکه اجدادش و فرزندان آن‌ها که با رأس $v$ فاصله‌ی حداکثر $k$ دارند را نیز بپوشاند. بنابراین در خروجی تابع علاوه بر فاصله‌ی دورترین فرزند پوشانده نشده، فاصله‌ی نزدیک ترین رأسی که روی آن مهره قرار دارد را نیز بر می‌گردانیم تا با استفاده از این مقدار، همه‌ی رأس‌های پوشیده شده توسط مهره‌ها را محاسبه کنیم. اثبات صحت این الگوریتم، به شکل کلی اثبات الگوریتم‌های حریصانه است و به خواننده واگذار می‌شود.

با الگوریتم بالا ما توانستیم رئوس درخت را به کم‌ترین تعداد مجموعه افراز کنیم که فقط در شرط دوم صدق کنند. شرط اول از ما می‌خواهد که اندازه‌ی هر مجموعه از $s$ بیش‌تر نشود. با در نظر گرفتن این شرط تغییری که باید در الگوریتم ایجاد کنیم این است که هر مهره دارای ظرفیت است و باید هر یک از رئوس را به‌یک مهره نسبت داد. یعنی ممکن است یک مهره تعداد زیادی از رئوس را بپوشاند، اما فقط تعدادی از آن‌ها بتواند در مجموعه‌ی متناظر با آن مهره قرار گیرد، چون یک مهره ظرفیت محدودی دارد. بنابراین وقتی در الگوریتم حریصانه‌ی بالا به رأسی مثل $v$ رسیدیم که فاصله‌ی دورترین رأس پوشیده نشده از آن $k$ بود، علاوه بر این که تعیین می‌کنیم که در $v$ باید یک مهره باشد، مشخص می‌کنیم که این مهره با چه رئوسی در ارتباط باشد. مجموعه‌ی رئوسی را که با $v$ به فاصله $k$ قرار دارند، $A$ می‌نامیم. به طور حریصانه می‌توان اثبات کرد که مهره‌ی جدید می‌تواند با هر یک از اعضای $A$ در ارتباط باشد. بنابراین اگر $t=\lceil(|A|)/s\rceil$ در این صورت ما $t$ مهره روی راس $v$ قرار می‌دهیم. هر یک از این $t$ مهره را به جز حداکثر یک مهره مثل $m$ ، با $s$ تا از رئوس مجموعه $A$ مرتبط می‌سازیم و مهره‌ی $m$ را با بقیه‌ی اعضای $A$ مرتبط می‌کنیم. مهره‌ی $m$ هنوز ظرفیت خالی دارد اما با توجه به اینکه ممکن است بقیه‌ی رئوس مرتبط با $m$ خارج از زیر درخت $v$ باشند، ظرفیت خالی $m$ را در مراحل بعدی DFS پر می‌کنیم.

بنابراین الگوریتم DFS اولیه را اینگونه تغییر می‌دهیم که پس از اتمام DFS یک رأس مثل $v$، به عنوان خروجی، لیستی از رئوسی که در زیر درخت $v$ هستند و هنوز توسط مهره‌ای پوشیده نشده‌اند و همچنین لیستی از مهره‌هایی که در زیر درخت $v$ هستند و ظرفیت خالی دارند را بر‌می‌گردانیم. حال وقتی که در حال اجرای DFS رأسی مثل $u$ هستیم، در ابتدا DFS همه بچه‌های $u$ را فراخوانی می‌کنیم. لیست رئوس پوشیده نشده‌ی همه‌ی بچه‌های $u$ را با هم ادغام می‌کنیم. همچنین لیست همه‌ی مهره‌های با ظرفیت خالی را نیز ادغام می‌کنیم. اگر در بین لیست بچه‌های پوشیده نشده، رئوسی با فاصله‌ی $k$ از رأس $u$ قرار داشند، آن‌ها را از این لیست جدا می‌کنیم و در مجموعه‌ی $A$ قرار می‌دهیم. این رئوس، رئوسی هستند که باید در این مرحله از DFS، مهره‌ی متناظرشان مشخص شود. بنابراین اگر چنین رئوسی وچود نداشتند (یعنی $|A| = 0$ )در این صورت DFS رأس $u$ را خاتمه می‌دهیم و دو لیست مریوطه را به عنوان خروجی بر می‌گردانیم. اما اگر $|A| > 0$، سعی می‌کنیم که رئوس مجموعه‌ی $A$ را با استفاده از لیست مهره‌های موجود بپوشانیم. برای این کار به صورت حریصانه عمل می‌کنیم. یعنی ابتدا سراغ مهره‌ای می‌رویم که عمق بیش‌تری دارد و در آینده کم‌تر به درد می‌خورد. هر تعداد از رئوس مجموعه‌ی $A$ را که می‌توانیم با این مهره می‌پوشانیم. در صورتی که ظرفیت این مهره پر شود آن را از لیست مهره‌های ظرفیت دار حذف می‌کنیم. سپس سراغ مهره‌ی بعدی (به ترتیب نزولی عمق مهره ها) می‌رویم و همین‌طور ادامه می‌دهیم. اگر در نهایت تعدادی از این رئوس باقی بماند، به میزان لازم مهره روی رأس $u$ قرار می‌دهیم و در صورتی که مهره‌ای با ظرفیت خالی به وجود آمد آن را به لیست مهره‌ها اضافه می‌کنیم. در انتها لیست مهره‌ها و رئوس باقی‌مانده را به عنوان خروجی برمی‌گردانیم. علاوه بر این بعد از اینکه کل DFS ها تمام شد، باید رئوس باقی‌مانده در لیست خروجی را به‌وسیله‌ی گذاشتن مهره در ریشه‌ی درخت DFS پوشاند.

با توجه به حریصانه بودن الگوریتم، با استفاده از روش معمولِ اثبات الگوریتم‌های حریصانه، (یعنی در نظر گرفتن اولین تفاوت جواب الگوریتم ما با جواب بهینه و شبیه کردن دو جواب به هم) می‌توان نشان داد که الگوریتم ما جواب بهینه را تولید می‌کند که با توجه به طولانی شدن راه حل اثبات این بخش نیز به خواننده واگذار می‌شود.

پیچیدگی

بنابراین کل الگوریتم به صورت بازگشتی و در یک DFS خلاصه می‌شود. تابع DFS به ازای هر رأسی مثل $v$ که صدا زده شد، به ترتیب کارهای زیر را انجام می‌دهیم:

 
-  	   تابع DFS را برای همه‌ی بچه‌های $v$ صدا می‌زنیم.
-     	در بین رأس‌های پوشیده نشده‌ی از نوادگان $v$ ، آن‌هایی که فاصله شان تا $v$ دقیقا $k$ می‌باشد را در مجموعه‌ی $A$ می‌ریزیم.
-     	مهره‌هایی که در زیردرخت $v$ قرار دارند و هنوز ظرفیت خالی دارند را به ترتیب نزولی عمق‌شان بررسی می‌کنیم و به ازای هر یک تا حد امکان، رئوس $A$ را می‌پوشانیم.
-     	در صورتی که هنوز مجموعه‌ی $A$ رأسی پوشیده نشده دارد، به تعداد لازم ($t=\lceil(|A|)/s\rceil$) مهره در رأس $v$ قرار می‌دهیم.
    

برای اینکه الگوریتم زمان اجرای مناسبی داشته باشد، باید هر یک از مراحل بالا را به شکل بهینه انجام داد. مثلا برای یافتن سریع مجموعه‌ی $A$ می‌توانیم بعد از اتمام DFS هر رأس، آن را در یک آرایه از لیست‌ها که رئوس پوشیده نشده را برحسب عمق نگهداری می‌کند، قرار دهیم. در این صورت برای یافتن رئوسی که از $v$ فاصله‌ی $k$ دارند کافی است که لیست $d[v] + k$ ام این آرایه را بررسی کنیم که $d[v]$ برابر عمق $v$ است (البته چون قبلا ممکن است این لیست پر شده باشد، باید قسمت انتهایی این لیست که مربوط به زیردرخت $v$ است را بررسی کنیم).

اگر هر یک از قسمت‌های الگوریتم به شکل بهینه انجام شود، با توجه به اینکه در هر مرحله از DFS تعداد مهره‌ی‌های دارای ظرفیت خالی کم است، زمان اجرای الگوریتم بسیار کم و به طور شهودی چیزی در حدود $O(n \log n)$ می‌شود.