الگوریتم کارگر

گرافی با دو برش. خط چین قرمز رنگ برشی با سه یال عبوری و خط چین سبز رنگ برش کمینه این گراف است که تنها از دو یال عبور می‌کند
در علوم رایانه و نظریه گراف، الگوریتم کارگر یک الگوریتم تصادفی برای محاسبه برش کمینه از یک گراف هم بند است. این الگوریتم توسط
دیوید کارگر
اختراع و در سال ۱۹۹۳ برای نخستین بار چاپ شد.
ایده الگوریتم مبنی بر مفهوم تلفیق یال در گراف بدون جهت است. به بیان غیر رسمی، تلفیق یک یال راس‌های و را در هم ادغام می‌کند و تعداد کل راس‌های گراف را یکی کاهش می‌دهد. همه یال‌های دیگر که یا به یا به متصل هستند، به راس ادغامی «دوباره ضمیمه می‌شوند» و در عمل یک گراف چندگانه تولید می‌شود. الگوریتم اصلی کارگر یکی پس از دیگری یال‌هایی را که به صورت تصادفی انتخاب شده‌اند با هم تلفیق می‌کند تا فقط دو راس باقی بماند؛ آن دو راس نمایانگر یک برش در گراف اولیه هستند. با تکرار این الگوریتم تا زمانی که دو راس باقی بماند، با احتمال موفقیت زیادی می‌توان یک برش کمینه پیدا کرد.
مسئله جهانی برش کمینه
یک برش در یک گراف بدون جهت افرازی از راس‌های به دو مجموعه غیر تهی و مجزای است.
مجموعه برش یک برش، از یال‌های بین دو بخش برش تشکیل می‌شود. اندازه (یا وزن) یک برش در یک گراف بدون جهت تعداد اعضای مجموعه برش، یعنی تعداد یال‌های بین دو بخش، است،
روش انتخاب برای هر راس چه متعلق به و چه وجود دارد، اما دو مورد از این انتخاب‌ها یا را تهی می‌کنند و برش تولید نمی‌کنند. در میان انتخاب‌های باقی‌مانده، تعویض نقش‌های و برش را تغییر نمی‌دهد، بنابراین هر برش دو بار شمارش می‌شود؛ پس برش متمایز وجود دارد.
مسئله برش کمینه می‌خواهد برشی با کوچک‌ترین اندازه در میان این برش‌ها بیابد.
برای گراف‌های وزن دار با یال‌هایی با وزن مثبت وزن برش، حاصل جمع وزن‌های یال‌های بین رئوس در هر بخش است
که با تعریف بدون وزن برای مطابقت دارد.
یک برش گاهی یک «برش جهانی» نامیده می‌شود تا از یک «برش - » برای زوج داده شده‌ای از رئوس، که شرط اضافه و را دارد، تمایز داده شود. هر برش جهانی یک برش - برای یک است. بنابراین، مسئله برش کمینه می‌تواند با یکی یکی پیش رفتن در میان همه انتخاب‌های و حل مسئله برش - کمینه حاصله با استفاده از قضیه جریان بیشینه برش کمینه و یک الگوریتم با زمان چندجمله‌ای برای مسئله بیشینه جریان، مانند الگوریتم فورد-فالکرسون، در زمان چندجمله‌ای حل شود، گرچه این رویکرد بهینه نیست. یک الگوریتم تعیین کننده برای مسئله برش کمینه با زمان اجرای وجود دارد.
الگوریتم تلفیق
عملکرد بنیادی الگوریتم کارگر شکلی از تلفیق یالی است. نتیجه تلفیق یال راس تازه خواهد بود. هر یال یا برای در دو انتهای یال تلفیقی با یک یال به راس تازه جایگزین می‌شود. سرانجام، رئوس تلفیقی و با همه یال‌های واقع بر آن حذف می‌شوند. به ویژه گراف حاصل هیچ حلقه‌ای را در بر ندارد. نتیجه تلفیق یال با نشان داده می‌شود.
راس مشخص شده به یک راس تلفیق شده است.
الگوریتم تلفیق مرتبا یال‌های تصادفی را در گراف تلفیق می‌کند تا زمانی که فقط دو راس باقی بماند که آنگاه فقط یک برش یکتا وجود دارد.
اجرای موفق الگوریتم کارگر روی یک گراف ۱۰ راسی. تعداد یال‌های برشی کمینه ۳ است.
procedure contract( ):
while
choose uniformly at random
return the only cut in
وقتی گراف با استفاده از لیست‌های مجاورت یا ماتریس مجاورت نمایش داده می‌شود، یک عمل یکتای تلفیق یالی را می‌توان با تعدادی بروزرسانی با زمان اجرای خطی روی داده ساختار، با زمان اجرای کل ، پیاده سازی کرد. از سوی دیگر، این روند را می‌توان به منزله اجرای الگوریتم کروسکال برای ایجاد درخت فراگیر کمینه در گرافی که یال‌هایش بر اساس یک جایگشت تصادفی وزن‌های دارند دید. حذف سنگین‌ترین یال این درخت به ایجاد دو مولفه می‌انجامد که یک برش را توصیف می‌کنند. به این روش، روند تلفیق را می‌تواند مانند الگوریتم کروسکال در زمان پیاده سازی کرد.
انتخاب یال‌های تصادفی در الگوریتم کارگر مربوط به اجرای الگوریتم کروسکال روی گرافی با مرتبه یال‌های تصادفی تا زمانی که فقط دو مولفه باقی بماند.
بهترین پیاده سازی‌های شناخته شده، به ترتیب از زمان و فضای یا زمان و فضای
استفاده می‌کنند.
احتمال موفقیت الگوریتم تلفیقی
در گراف با راس، الگوریتم تلفیقی با احتمال یک برش کمینه برمی گرداند. در میان برش گراف، حد اکثر برش کمینه وجود دارد، بنابراین این احتمال بسیار بهتر از انتخاب یک برش به صورت تصادفی است.
برای مثال، گراف دوری روی راس، دقیقا برش کمینه دارد، که از انتخاب هر دو یال به دست می‌آید. روند تلفیق با احتمال برابر هر یک از این یال‌ها را می‌یابد.
برای آن که کران احتمال موفقیت را به طور کلی به دست آوریم، اگر یال‌های یک برش کمینه خاص با اندازه را با نشان دهیم آنگاه الگوریتم تلفیق را برمی گرداند اگر و فقط اگر هیچ یک از یال‌های تصادفی در مجموعه برش نباشد. به ویژه، اولین تلفیق یالی از اجتناب می‌کند، که با احتمال رخ می‌دهد. درجه کمینه حد اقل است (در غیر این صورت یک راس با درجه کمینه یک برش کوچک‌تر را سبب می‌شد)، بنابراین . پس احتمال این که الگوریتم تلفیق، یالی از را برگزیند برابر است با:
احتمال که الگوریتم تلفیق روی یک گراف راسی از اجتناب کند، در رابطه بازگشتی با صدق می‌کند که می‌توان آن را به صورت زیر بسط داد:
p_n \geq \prod_{i=0^{n-3 \Bigl(1-\frac{2{n-i\Bigr) =
\prod_{i=0^{n-3 {\frac{n-i-2{n-i
= \frac{n-2{n\cdot \frac{n-3{n-1 \cdot \frac{n-4{n-2\cdots \frac{3{5\cdot \frac{2{4 \cdot \frac{1{3
= \binom{n{2^{-1\,.
تکرار الگوریتم تلفیق
۱۰بار تکرار الگوریتم تلفیق. در پنجمین تکرار، الگوریتم برش کمینه را با اندازه ۳ پیدا می‌کند.
با تکرار بار الگوریتم تلفیق با انتخاب‌های مستقل تصادفی و برگرداندن کوچک‌ترین برش، احتمال پیدا نکردن برش کمینه عبارتست از:
\Bigl1-\binom{n{2^{-1\Bigr^T
\leq \frac{1{e^{\ln n = \frac{1{n\,.
زمان اجرای کل برای بار تکرار برای گرافی با راس و یال برابر است با:
الگوریتم کارگر_اشتاین
یک بسط الگوریتم کارگر، توسط دیوید کارگر و کلیفورد اشتاین به بهبود مرتبه زمانی حالت قبل منجر می‌شود.
ایده اصلی این است که رویه تلفیق تا زمانی که گراف به راس برسد انجام شود.
procedure contract( , ):
while
choose uniformly at random
return
احتمال که این رویه تلفیق از یک برش خاص در یک گراف راسی اجتناب کند چنین است:
\begin{align
p_{n,t -\ge \prod_{i=0^{n-t-1 \Bigl(1-\frac{2{n-i\Bigr) = \binom{t{2\bigg/\binom{n{2\,.
\end{align
این عبارت از است و از حول
کمتر می‌شود. به ویژه احتمال این که یک یال از تلفیق شود تا پایان افزایش می‌یابد. این انگیزه ایده تغییر به یک الگوریتم کندتر پس از تعداد معینی گام‌های تلفیقی است.
procedure fastmincut( ):
if :
return mincut( )
else :
contract( , )
contract( , )
return min {fastmincut( ), fastmincut( )
تجزیه و تحلیل
احتمال را احتمال پیداکردن یک مجموعه برش خاص توسط الگوریتم در نظر بگیریم آنگاه با رابطه بازگشتی زیر داده می‌شود:
که راه حل آن است. زمان اجرای سریع‌ترین برش کمینه در
در راه حل صدق می‌کند.
برای رسیدن به احتمال خطای ، الگوریتم می‌تواند بار تکرار گردد، با زمان اجرای کل این یک مرتبه زمانی با بهبود زیاد روی الگوریتم اصلی کارگر است.
یافتن همه برش‌های کمینه
قضیه: با احتمال زیادی می‌توان همه برش‌های کمینه را در زمان اجرای یافت.
اثبات: از آنجا که می‌دانیم ، بنابراین پس از اجرای این الگوریتم به تعداد بار، احتمال از بین رفتن یک برش کمینه خاص چنین است:
و حداکثر برش کمینه وجود دارد، بنابراین احتمال از دست دادن هر برش کمینه چنین است:
وقتی n به اندازه کافی بزرگ باشد، احتمال شکست به نحو قابل ملاحظه‌ای کم خواهد بود. ∎
کران بهبود
برای تعیین برش کمینه، باید از هر یال در گراف حداقل یک بار بگذریم، که در یک گراف چگال از است. الگوریتم برش کمینه کارگر_اشتاین زمان اجرای می‌برد، که خیلی به آن نزدیک است.