الگوریتم کارگر
در علوم رایانه و نظریهٔ گراف، الگوریتم کارگِر یک الگوریتم تصادفی برای محاسبهٔ برش کمینه از یک گراف هم بند است. این الگوریتم توسط دیوید کارگر اختراع و در سال ۱۹۹۳ برای نخستین بار چاپ شد.
ایدهٔ الگوریتم مبنی بر مفهوم تلفیق یال formula_1 در گراف بدون جهت formula_2 است. به بیان غیر رسمی، تلفیق یک یال رأس‌های formula_3 و formula_4 را در هم ادغام می‌کند و تعداد کل رأس‌های گراف را یکی کاهش می‌دهد. همهٔ یال‌های دیگر که یا به formula_3 یا به formula_4 متصل هستند، به رأس ادغامی «دوباره ضمیمه می‌شوند» و در عمل یک گراف چندگانه تولید می‌شود. الگوریتم اصلی کارگر یکی پس از دیگری یال‌هایی را که به صورت تصادفی انتخاب شده‌اند با هم تلفیق می‌کند تا فقط دو رأس باقی بماند؛ آن دو رأس نمایانگر یک برش در گراف اولیه هستند. با تکرار این الگوریتم تا زمانی که دو راس باقی بماند، با احتمال موفقیت زیادی می‌توان یک برش کمینه پیدا کرد.
یک "برش" formula_7 در یک گراف بدون جهت formula_2 افرازی از رأس‌های formula_9 به دو مجموعهٔ غیر تهی و مجزای formula_10 است.
"مجموعه برش " یک برش، از یال‌های formula_11 بین دو بخش برش تشکیل می‌شود. "اندازه" (یا "وزن") یک برش در یک گراف بدون جهت تعداد اعضای مجموعه برش، یعنی تعداد یال‌های بین دو بخش، است، formula_12.
formula_13 روش انتخاب برای هر رأس چه متعلق به formula_14 و چه formula_15 وجود دارد، اما دو مورد از این انتخاب‌ها formula_14 یا formula_15 را تهی می‌کنند و برش تولید نمی‌کنند. در میان انتخاب‌های باقی‌مانده، تعویض نقش‌های formula_14 و formula_15 برش را تغییر نمی‌دهد، بنابراین هر برش دو بار شمارش می‌شود؛ پس formula_20.
احتمال formula_21 که الگوریتم تلفیق روی یک گراف formula_22 رأسی از formula_23 اجتناب کند، در رابطهٔ بازگشتی formula_24 با formula_25 صدق می‌کند که می‌توان آن را به صورت زیر بسط داد:
formula_26
با تکرار formula_27 بار الگوریتم تلفیق با انتخاب‌های مستقل تصادفی و برگرداندن کوچک‌ترین برش، احتمال پیدا نکردن برش کمینه عبارتست از: formula_28
زمان اجرای کل برای formula_15 بار تکرار برای گرافی با formula_22 رأس و formula_31 یال برابر است با: formula_32.
یک بسط الگوریتم کارگر، توسط دیوید کارگر و کلیفورد اشتاین به بهبود مرتبهٔ زمانی حالت قبل منجر می‌شود. ایدهٔ اصلی این است که رویهٔ تلفیق تا زمانی که گراف به formula_33 رأس برسد انجام شود. احتمال formula_40 که این رویهٔ تلفیق از یک برش خاص formula_23 در یک گراف formula_22 رأسی اجتناب کند چنین است:
formula_43
این عبارت از formula_44 است و از formula_45 حول formula_46 کمتر می‌شود. به ویژه احتمال این که یک یال از formula_23 تلفیق شود تا پایان افزایش می‌یابد. این انگیزهٔ ایدهٔ تغییر به یک الگوریتم کندتر پس از تعداد معینی گام‌های تلفیقی است. احتمال formula_60 را احتمال پیدا کردن یک مجموعهٔ برش خاص formula_23 توسط الگوریتم در نظر بگیریم آنگاه formula_60 با رابطهٔ بازگشتی زیر داده می‌شود:
formula_63
که راه حل آن formula_64 است. زمان اجرای سریع‌ترین برش کمینه در formula_65
در راه حل formula_66 صدق می‌کند.
برای رسیدن به احتمال خطای formula_67، الگوریتم می‌تواند formula_68 بار تکرار گردد، با زمان اجرای کل formula_69 این یک مرتبهٔ زمانی با بهبود زیاد روی الگوریتم اصلی کارگر است.
قضیه: با احتمال زیادی می‌توان همهٔ برش‌های کمینه را در زمان اجرای formula_70 یافت.
اثبات: از آنجا که می دانیم formula_71، بنابراین پس از اجرای این الگوریتم به تعداد formula_72 بار، احتمال از بین رفتن یک برش کمینهٔ خاص چنین است:
formula_73.
و حداکثر formula_74 برش کمینه وجود دارد، بنابراین احتمال از دست دادن هر برش کمینه چنین است:
formula_75
وقتی "n" به اندازهٔ کافی بزرگ باشد، احتمال شکست به نحو قابل ملاحظه‌ای کم خواهد بود. ∎
برای تعیین برش کمینه، باید از هر یال در گراف حداقل یک بار بگذریم، که در یک گراف چگال از formula_76 است. الگوریتم برش کمینهٔ کارگر_اشتاین زمان اجرای formula_77 می‌برد، که خیلی به آن نزدیک است.