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

الگوریتم میانگین–خطی درخت پوشای کمینه (به انگلیسی: Minimum spanning tree) یک الگوریتم تصادفی برای یافت درخت پوشای کمینه در یک گراف وزن دار بدون راس تنها است.

این الگوریتم توسط دیوید کرگر، فیلیپ کلین و رابرت تارجان ابداع شده‌است. این الگوریتم متکی بر شیوه الگوریتم بروکا است که برای یافت درخت پوشای کمینه در زمانی خطی است. این الگوریتم تشکیل شده از الگوریتم تقسیم و حل، الگوریتم حریصانه و الگوریتم‌های تصادفی برای رسیدن به زمان خطی مورد نظر. الگوریتم‌های قطعی برای یافت درخت پوشای کمینه عبارتند از: الگوریتم‌های پریم، کروسکال، بروکا.

نمای کلی

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

حرکت بروکا

هر تکرار الگوریتم مبتنی بر الگوریتم بروفکا را یک گام در نظر می‌گیریم.

ورودی: یک گراف که راس تنها ندارد
یک گراف منقبض به وسیلهٔ جایگزینی مولفه‌های ساخته شده با یال‌های مرحله یک با یک راس بساز
تمام رأس‌های تنها، طوقه‌ها، یال‌های تکراری غیر کمینه را حذف کن
خروجی: یال‌های انتخاب شده در مرحله یک و گراف منقبض شدهٔ باقی‌مانده.

  Input: A graph G with no isolated vertices
  1 For each vertex v, select the lightest edge incident on v
  2 Create a contracted graph G' by replacing each component of G connected by the edges
selected in step 1 with a single vertex
  3 Remove all isolated vertices, self-loops, and non-minimal repetitive edges from G'
  Output: The edges selected in step 1 and the contracted graph G'

یک گام بروفکا از اردر m است (تعداد یال‌ها) زیرا هر یال حداکثر از دو طرفش دیده می‌شود. بعد از این مرحله تعداد مؤلفه‌ها حداکثر n/2 است. Example Execution of a Borůvka Step

عکس	خلاصه
	کوچکترین یال برای هر راس انتخاب می‌شود.
	هر مؤلفه‌ای ادغام می‌شود و تبدیل به یک ابرراس می‌شود.
	طوقه‌ها حذف می‌شوند.
	از بین یالهای چندگانه کوچکترین می‌ماند.
	در انتها یک گراف با دو ابرراس و یک یال باقی می‌ماند.

یالهای 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 برای همهٔ انتخاب‌ها یکی است. برای اثبات انتخاب یالها را از سبک به سنگین در نظر می‌گیریم.

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

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

منابع

• مشارکت کنندگان ویکی‌پدیا(Expected linear time MST algorithm)، در ویکی‌پدیای انگلیسی. بازبینی در ۲۷می ۲۰۱۹.