پاورپوینت حذف معکوس

بخشی از پاورپوینت

اسلاید 1 :

حذف معکوس

اسلاید 2 :

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

اسلاید 3 :

1. با گراف G که لیستی از یالهای E دارد شروع کرده.

2. E را به ترتیب نزولی وزن یالها مرتب کرده.

3. برای هر یال چک کرده که آیا حذف این یال گراف را ناهمبند میکند یا نه.

4. اگر حذف کردن منجر به ناهمبندی گراف نمیشود یال را حذف کرده.

اسلاید 6 :

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

اسلاید 7 :

میتوان نشان داد که الگوریتم در زمان (O(E log V (log log V)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 نادیده گرفته میشود.