الگوریتم کارگر کیست؟ توضیح بده.
در علوم رایانه و نظریهٔ گراف، الگوریتم کارگِر یک الگوریتم تصادفی برای محاسبهٔ برش کمینه از یک گراف هم بند است. این الگوریتم توسطدیوید کارگراختراع و در سال ۱۹۹۳ برای نخستین بار چاپ شد.ایدهٔ الگوریتم مبنی بر مفهوم تلفیق یال 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 رأس برسد انجام شود. procedure contract(formula_34, formula_33): while formula_36 choose formula_37 uniformly at random formula_38 return formula_39احتمال formula_40 که این رویهٔ تلفیق از یک برش خاص formula_23 در یک گراف formula_22 رأسی اجتناب کند چنین است:formula_43این عبارت از formula_44 است و از formula_45 حولformula_46 کمتر می‌شود. به ویژه احتمال این که یک یال از formula_23 تلفیق شود تا پایان افزایش می‌یابد. این انگیزهٔ ایدهٔ تغییر به یک الگوریتم کندتر پس از تعداد معینی گام‌های تلفیقی است. procedure fastmincut(formula_48): if formula_49: return mincut(formula_9) else: formula_51 formula_52 contract(formula_39, formula_33) formula_55 contract(formula_39, formula_33)تجزیه و تحلیل.احتمال 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 می‌برد، که خیلی به آن نزدیک است.