موضوع مقاله: الگوریتم کارگر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم کارگر | مقدمه: خط چین قرمز رنگ برشی با سه یال عبوری و خط چین سبز رنگ برش کمینهٔ این گراف است که تنها از دو یال عبور می‌کند در علوم رایانه و نظریهٔ گراف، الگوریتم کارگِر یک الگوریتم تصادفی برای محاسبهٔ برش کمینه از یک گراف هم بند است. | ## بخش 1: الگوریتم کارگر | به بیان غیر رسمی، تلفیق یک یال رأس‌های و را در هم ادغام می‌کند و تعداد کل رأس‌های گراف را یکی کاهش می‌دهد. همهٔ یال‌های دیگر که یا به یا به متصل هستند، به رأس ادغامی «دوباره ضمیمه می‌شوند» و در عمل یک گراف چندگانه تولید می‌شود. الگوریتم اصلی کارگر یکی پس از دیگری یال‌هایی را که به صورت تصادفی انتخاب شده‌اند با هم تلفیق می‌کند تا فقط دو رأس باقی بماند؛ آن دو رأس نمایانگر یک برش در گراف اولیه هستند. با تکرار این الگوریتم تا زمانی که دو راس باقی بماند، با احتمال موفقیت زیادی می‌توان یک برش کمینه پیدا کرد. مسئلهٔ جهانی برش کمینه یک برش در یک گراف بدون جهت افرازی از رأس‌های به دو مجموعهٔ غیر تهی و مجزای است. اندازه (یا وزن) یک برش در یک گراف بدون جهت تعداد اعضای مجموعه برش، یعنی تعداد یال‌های بین دو بخش، است، . روش انتخاب برای هر رأس چه متعلق به و چه وجود دارد، اما دو مورد از این انتخاب‌ها یا را تهی می‌کنند و برش تولید نمی‌کنند. در میان انتخاب‌های باقی‌مانده، تعویض نقش‌های و برش را تغییر نمی‌دهد، بنابراین هر برش دو بار شمارش می‌شود؛ پس برش متمایز وجود دارد. برای گراف‌های وزن دار با یال‌هایی با وزن مثبت وزن برش، حاصل جمع وزن‌های یال‌های بین رئوس در هر بخش است که با تعریف بدون وزن برای مطابقت دارد. یک برش گاهی یک «برش جهانی» نامیده می‌شود تا از یک «برش -» برای زوج داده شده‌ای از رئوس، که شرط اضافهٔ و را دارد، تمایز داده شود. | ## بخش 2: الگوریتم کارگر | بنابراین، مسئلهٔ برش کمینه می‌تواند با یکی یکی پیش رفتن در میان همهٔ انتخاب‌های و حل مسئلهٔ برش - کمینهٔ حاصله با استفاده از قضیهٔ جریان بیشینهٔ برش کمینه و یک الگوریتم با زمان چندجمله‌ای برای مسئله بیشینه جریان، مانند الگوریتم فورد-فالکرسون، در زمان چندجمله‌ای حل شود، گرچه این رویکرد بهینه نیست. الگوریتم تلفیق مرتباً یال‌های تصادفی را در گراف تلفیق می‌کند تا زمانی که فقط دو رأس باقی بماند که آنگاه فقط یک برش یکتا وجود دارد. از سوی دیگر، این روند را می‌توان به منزلهٔ اجرای الگوریتم کروسکال برای ایجاد درخت فراگیر کمینه در گرافی که یال‌هایش بر اساس یک جایگشت تصادفی وزن‌های دارند دید. حذف سنگین‌ترین یال این درخت به ایجاد دو مؤلفه می‌انجامد که یک برش را توصیف می‌کنند. به این روش، روند تلفیق را می‌تواند مانند الگوریتم کروسکال در زمان پیاده‌سازی کرد. frame|وسط|انتخاب یال‌های تصادفی در الگوریتم کارگر مربوط به اجرای الگوریتم کروسکال روی گرافی با مرتبهٔ یال‌های تصادفی تا زمانی که فقط دو مؤلفه باقی بماند. بهترین پیاده سازی‌های شناخته شده، به ترتیب از زمان و فضای یا زمان و فضای استفاده می‌کنند. احتمال موفقیت الگوریتم تلفیقی در گراف با رأس، الگوریتم تلفیقی با احتمال یک برش کمینه برمی گرداند. در میان برش گراف، حد اکثر برش کمینه وجود دارد، بنابراین این احتمال بسیار بهتر از انتخاب یک برش به صورت تصادفی است. برای مثال، گراف دوری روی رأس، دقیقاً برش کمینه دارد، که از انتخاب هر دو یال به دست می‌آید. | ## بخش 3: الگوریتم کارگر | برای آن که کران احتمال موفقیت را به‌طور کلی به دست آوریم، اگر یال‌های یک برش کمینهٔ خاص با اندازهٔ را با نشان دهیم آنگاه الگوریتم تلفیق را برمی گرداند اگر و فقط اگر هیچ یک از یال‌های تصادفی در مجموعهٔ برش نباشد. درجهٔ کمینهٔ حد اقل است (در غیر این صورت یک رأس با درجهٔ کمینه یک برش کوچک تر را سبب می‌شد)، بنابراین . با تکرار بار الگوریتم تلفیق با انتخاب‌های مستقل تصادفی و برگرداندن کوچک‌ترین برش، احتمال پیدا نکردن برش کمینه عبارتست از: زمان اجرای کل برای بار تکرار برای گرافی با رأس و یال برابر است با: . الگوریتم کارگر_اشتاین یک بسط الگوریتم کارگر، توسط دیوید کارگر و کلیفورد اشتاین به بهبود مرتبهٔ زمانی حالت قبل منجر می‌شود. این انگیزهٔ ایدهٔ تغییر به یک الگوریتم کندتر پس از تعداد معینی گام‌های تلفیقی است. برای رسیدن به احتمال خطای ، الگوریتم می‌تواند بار تکرار گردد، با زمان اجرای کل این یک مرتبهٔ زمانی با بهبود زیاد روی الگوریتم اصلی کارگر است. یافتن همهٔ برش‌های کمینه قضیه: با احتمال زیادی می‌توان همهٔ برش‌های کمینه را در زمان اجرای یافت. اثبات: از آنجا که می دانیم ، بنابراین پس از اجرای این الگوریتم به تعداد بار، احتمال از بین رفتن یک برش کمینهٔ خاص چنین است: . و حداکثر برش کمینه وجود دارد، بنابراین احتمال از دست دادن هر برش کمینه چنین است: وقتی n به اندازهٔ کافی بزرگ باشد، احتمال شکست به نحو قابل ملاحظه‌ای کم خواهد بود. | ## جمع‌بندی | ∎ کران بهبود برای تعیین برش کمینه، باید از هر یال در گراف حداقل یک بار بگذریم، که در یک گراف چگال از است.