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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم میانگین–خطی درخت پوشای کمینه یک الگوریتم تصادفی برای یافت درخت پوشای کمینه در یک گراف وزن دار بدون راس تنها است.

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

نمای کلی[ویرایش]

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

حرکت بروکا[ویرایش]

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

ورودی: یک گراف که راس تنها ندارد
یک گراف منقبض به وسیله ی جایگزینی مولفه های ساخته شده با یال های مرحله یک با یک راس بساز
تمام راس های تنها، طوقه ها، یال های تکراری غیر کمینه را حذف کن
خروجی: یال های انتخاب شده در مرحله یک و گراف منقبض شده ی باقی‌مانده.
  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

عکس خلاصه
Boruvka Step 1.svg کوچکترین یال برای هر راس انتخاب می شود.
Boruvka Step 2.svg هر مولفه ای ادغام می شود و تبدیل به یک ابرراس می شود.
Boruvka Step 3.svg طوقه ها حذف می شوند.
Boruvka Step 4.svg از بین یالهای چندگانه کوچکترین می ماند.
Boruvka Step 5.svg در انتها یک گراف با دو ابرراس و یک یال باقی می ماند.

یالهای 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 ها را در زمان مورد نظر خطی محاسبه کرد.

الگوریتم[ویرایش]

یک گراف که راس تنها ندارد بگیر
اگر گراف تهی بود یک جنگل تهی بده
یک گراف منقبض با اجرای 2 مرحله پی در پی بروفکا بساز
یک زیر گراف با انتخاب یال ها به احتمال (2/1) بساز و درخت پوشای کمینه ی آن را بیاب
با استفاده از 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 برای همه ی انتخاب ها یکی است. برای اثبات انتخاب یالها را از سبک به سنگین در نظر می گیریم.

تحلیل میانگین[ویرایش]

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

منابع[ویرایش]