الگوریتم میانگین–خطی درخت پوشای کمینه

نمای کلی

کلید این الگوریتم تقسیم تصادفی گراف به دو زیرگراف و تقسیم یال‌ها بین این زیرگراف هاست. الگوریتم به صورت بازگشتی جواب را برای یک زیرگراف می‌یابد و سپس آن را به کل گراف تعمیم می‌دهد. روش گرفته شده از [الگوریتم برفکا] برای کاهش حجم گراف در هر مرحله بازگشتی است.

یالهای F-heavy و F-light

در هر تقسیم یال‌هایی با خواصی که آن‌ها را از بودن در درخت پوشای کمینه محروم می‌کند حذف می‌شوند. این یال‌ها را F-heavy می‌نامیم که این گونه اند: فرض کنید F یک جنگل پوشای کمینه از گراف H است، یک F-heavy یالی است که رأس‌های u و v را به هم دیگر متصل می‌کند که وزنش از وزن بیشترین یال مسیر u و v در F بیشتر است. هر یالی که F-heavy نیست F-light نام دارد. اگر H یک زیرگراف از G باشد، هیچ F-heavy نمی‌تواند در درخت کمینه باشد. برای گراف G می‌توان F-heavyها را در زمان مورد نظر خطی محاسبه کرد.

الگوریتم

یک گراف که راس تنها ندارد بگیر
اگر گراف تهی بود یک جنگل تهی بده
یک گراف منقبض با اجرای ۲ مرحله پی در پی بروفکا بساز
یک زیر گراف با انتخاب یال‌ها به احتمال (۲/۱) بساز و درخت پوشای کمینهٔ آن را بیآب
با استفاده از linear time minimum spanning tree verification algorithm تمام F-heavyها را حذف کن
به صورت بازگشتی درخت پوشای کمینه را برای 'G بدست بیاور
درخت پوشای کمینهٔ 'G و یال‌های منتخب بروفکا را چاپ کن
Input: A graph G with no isolated vertices
  1 If G is empty return an empty forest
  2 Create a contracted graph G' by running two successive Borůvka steps on G
  3 Create a subgraph H by selecting each edge in G' with probability 1/2.
  Recursively apply the algorithm to H to get its minimum spanning forest F.
  4 Remove all F-heavy edges from G' (where F is the forest from step 3)
 using a linear time minimum spanning tree verification algorithm.
  5 Recursively apply the algorithm to G' to get its minimum spanning forest.
 Output: The minimum spanning forest of G' and the contracted edges from the Borůvka steps

درستی الگوریتم

درستی الگوریتم را با استقرا روی تعداد رئوس گراف ثابت می‌کنیم. پایه به وضوح درست است. T را د.پ. ک (درخت پوشای کمینه) ی G در نظر می‌گیریم. هر یال انتخاب شده در گام بروکا از همهٔ یالهال کات آن سوپرراس‌ها و همچنین دورهای شامل آن کوچکتر است. هر یال F-heavy حذف شده نیز در د.پ. ک نیست زیرا در دوری است که یال کوچکتر از آن وجود دارد یا در هیچ کاتی نیست که کوچکترین یال باشد.
همچنین حداکثر تعداد یالهای F-light که به گراف اضافه می‌شود برابر n-1 است و هر د.پ. ک ای نیز n-1 یال دارد. پس تعداد یالهای درخت محدود به یالهای F-heavy است و یالهای F-heavy نیز n-1 تاست. پس د.پ. ک ساخته می‌شود.

کارایی

کارایی در صورتی تضمین می‌شود که نمونه‌گیری تصادفی باشد. اثر مرحله نمونه‌گیری تصادفی، توسط لم زیر که یک حد بر روی تعداد یال‌های F-light در G در نتیجه محدود کردن اندازه زیر مسئله دوم است توصیف شده.

لم تصادفی

لم، نشان می‌دهد اگر H زیرگرافی از G باشد به گونه‌ای که هر یال G به احتمال p در آن باشد، و F د.پ. ک H باشد، تعداد یالهای F-light در G حداکثر n/p است (n تعداد رئوس G است).
برای اثبات لم تعداد یالهای G که به H اضافه شده‌اند را حساب می‌کنیم. تعداد یالهای F-light در G بستگی به روش انتخاب H دارد در حالیکه د.پ. ک H برای همهٔ انتخاب‌ها یکی است. برای اثبات انتخاب یالها را از سبک به سنگین در نظر می‌گیریم.

تحلیل میانگین

با نادیده گرفتن کار انجام شده در زیر مسئله بازگشتی مقدار کل کار انجام شده در یک فراخوانی از الگوریتم، کاری خطی تعداد یالهای گراف ورودی است. مرحلهٔ اول زمان ثابت می‌خواهد. گام‌های بروکا می‌توانند در زمان خطی به نحو گفته شده محاسبه شوند.