الگوریتم حذف معکوس

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

در نظریهٔ گراف الگوریتم حذف معکوس(به انگلیسی: Reverse-delete algorithm) الگوریتمی است که در یک گراف همبند، با یال وزن دار درخت پوشای کمینه را بدست می‌آورد. اگر گراف ناهمبند باشد این الگوریتم درخت پوشای کمینه را برای هر مولفهٔ همبندی می‌یابد که در این صورت مجموعهٔ این درخت‌های پوشای کمینه را یک جنگل پوشای کمینه گویند.

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

  • با گراف G که لیستی از یال‌های E دارد شروع کن.
  • E را به ترتیب نزولی وزن یال‌ها مرتب کن.
  • برای هر یال چک کن که آیا حذف این یال گراف را ناهمبند می‌کند یا نه.
  • اگر حذف کردن منجر به ناهمبندی گراف نمی‌شود یال را حذف کن

اثبات درستی[ویرایش]

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

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

 1  function ReverseDelete(edges[] E)
 2    sort E in decreasing order
 3    Define an index i ← 0
 4    while i <size(E)
 5       Define edge tempE[i]
 6         delete E[i]
 7         if temp.v1 is not connected to temp.v2
 8             E[i] ← temp
 9         ii + 1
 10   return edges[] E

در بالا گراف، مجوعه یال‌های وزن دار E است که هر یال آن وزنی دارد و دو راس v1 و v2 را به هم متصل می‌کند.

مثال[ویرایش]

در مثال زیر یال‌های سبز توسط الگوریتم انتخاب شده‌اند و یال‌های قرمز حذف شده‌اند.

Reverse Delete 0.svg این گراف اصلی است. اعداد کنار هر یال وزن هر یال را نشان می‌دهد.
Reverse Delete 1.svg الگوریتم با یال با بیشترین وزن که در اینجا یال DE با وزن ۱۵ است شروع به کار می‌کند. چون حذف یال DE گراف را ناهمبند نمی‌کند الگوریتم این یال را حذف می‌کند.
Reverse Delete 2.svg بزرگ ترین یال بعدی یال FG می‌باشد. الگوریتم چک می‌کند که آیا حذف این یال گراف را ناهمبند خواهد کرد. چون با حذف این یال گراف ناهمبند نمی‌شود این یال هم حذف خواهد شد.
Reverse Delete 3.svg بزرگ ترین یال بعدی یال BD می‌باشد. الگوریتم یال را چک می‌کند و سپس حذف می‌کند.
Reverse Delete 4.svg یال بعدی که چک می‌شود یال EG است که حذف نخواهد شد چون حذف شدن این یال گراف را ناهمبند خواهد کرد. بنابراین یال بعدی که باید حذف شود یال BC می‌باشد.
Reverse Delete 5.svg بزرگ ترین یال بعدی یال EF است که الگوریتم آن را چک می‌کند و حذف می‌کند.
Reverse Delete 6.svg الگوریتم باقی گراف را برای یافتن یالی برای حذف کردن می‌گردد اما یالی پیدا نمی‌کند بنابر این این گراف پایانی است که توسط الگوریتم بازگردانده می‌شود.

زمان اجرا[ویرایش]

می‌توان نشان داد که الگوریتم در زمان (O(E log E (log log E)3 انجام می‌شود که E تعداد یال‌ها و V تعداد گره‌های گراف است. این حد به صورت زیر محاسبه شده‌است:

مرتب سازی یال‌ها با استفاده از الگوریتم مرتب سازی مقایسه‌ای در زمان (O(E log E انجام می‌گیرد حلقه E بار تکرار می‌شود.

حذف کردن یال در(O(1 زمان انجام می‌گیرد.

همبندی در زمان (O(log V (log log V)3 انجام می‌گیرد.

زمان اجرا را می‌توان (O(E log V (log log V)3 در نظر گرفت زیرا E حداکثر V2 است. یادآوری log V2 = 2 * log V که ثابت ۲ در نوشتار big-O نادیده گرفته می‌شود.[۱]

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

  1. مشارکت‌کنندگان ویکی‌پدیا، «Reverse-delete algorithm»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۱ نوامبر ۲۰۱۰).