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

گرافی با دو برش. خط چین قرمز رنگ برشی با سه یال عبوری و خط چین سبز رنگ برش کمینهٔ این گراف است که تنها از دو یال عبور می‌کند

در علوم رایانه و نظریهٔ گراف، الگوریتم کارگِر (به انگلیسی: Karger's algorithm) یک الگوریتم تصادفی برای محاسبهٔ برش کمینه از یک گراف هم بند است. این الگوریتم توسط دیوید کارگر اختراع و در سال ۱۹۹۳ برای نخستین بار چاپ شد.

ایدهٔ الگوریتم مبنی بر مفهوم تلفیق یال $(u,v)$ در گراف بدون جهت $G=(V,E)$ است. به بیان غیر رسمی، تلفیق یک یال رأس‌های $u$ و $v$ را در هم ادغام می‌کند و تعداد کل رأس‌های گراف را یکی کاهش می‌دهد. همهٔ یال‌های دیگر که یا به $u$ یا به $v$ متصل هستند، به رأس ادغامی «دوباره ضمیمه می‌شوند» و در عمل یک گراف چندگانه تولید می‌شود. الگوریتم اصلی کارگر یکی پس از دیگری یال‌هایی را که به صورت تصادفی انتخاب شده‌اند با هم تلفیق می‌کند تا فقط دو رأس باقی بماند؛ آن دو رأس نمایانگر یک برش در گراف اولیه هستند. با تکرار این الگوریتم تا زمانی که دو راس باقی بماند، با احتمال موفقیت زیادی می‌توان یک برش کمینه پیدا کرد.

مسئلهٔ جهانی برش کمینه

یک برش $(S,T)$ در یک گراف بدون جهت $G=(V,E)$ افرازی از رأس‌های $V$ به دو مجموعهٔ غیر تهی و مجزای $S\cup T=V$ است.

مجموعه برش یک برش، از یال‌های $\{\,uv\in E\colon u\in S,v\in T\,\}$ بین دو بخش برش تشکیل می‌شود. اندازه (یا وزن) یک برش در یک گراف بدون جهت تعداد اعضای مجموعه برش، یعنی تعداد یال‌های بین دو بخش، است، $w(S,T)=|\{\,uv\in E\colon u\in S,v\in T\,\}|\,$.

$2^{|V|}$ روش انتخاب برای هر رأس چه متعلق به $S$ و چه $T$ وجود دارد، اما دو مورد از این انتخاب‌ها $S$ یا $T$ را تهی می‌کنند و برش تولید نمی‌کنند. در میان انتخاب‌های باقی‌مانده، تعویض نقش‌های $S$ و $T$ برش را تغییر نمی‌دهد، بنابراین هر برش دو بار شمارش می‌شود؛ پس $2^{|V|-1}-1$ برش متمایز وجود دارد. مسئلهٔ برش کمینه می‌خواهد برشی با کوچک‌ترین اندازه در میان این برش‌ها بیابد.

برای گراف‌های وزن دار با یال‌هایی با وزن مثبت $w\colon E\rightarrow \mathbf {R} ^{+}$ وزن برش، حاصل جمع وزن‌های یال‌های بین رئوس در هر بخش است $w(S,T)=\sum _{uv\in E\colon u\in S,v\in T}w(uv)\,,$

که با تعریف بدون وزن برای $w=1$ مطابقت دارد.

یک برش گاهی یک «برش جهانی» نامیده می‌شود تا از یک «برش $t$-$s$» برای زوج داده شده‌ای از رئوس، که شرط اضافهٔ $s\in S$ و $t\in T$ را دارد، تمایز داده شود. هر برش جهانی یک برش $t$-$s$ برای یک $s,t\in V$ است. بنابراین، مسئلهٔ برش کمینه می‌تواند با یکی یکی پیش رفتن در میان همهٔ انتخاب‌های $s,t\in V$ و حل مسئلهٔ برش $t$-$s$ کمینهٔ حاصله با استفاده از قضیهٔ جریان بیشینهٔ برش کمینه و یک الگوریتم با زمان چندجمله‌ای برای مسئله بیشینه جریان، مانند الگوریتم فورد-فالکرسون، در زمان چندجمله‌ای حل شود، گرچه این رویکرد بهینه نیست. یک الگوریتم تعیین‌کننده برای مسئلهٔ برش کمینه با زمان اجرای $O(mn+n^{2}\log n)$ وجود دارد.

الگوریتم تلفیق

عملکرد بنیادی الگوریتم کارگر شکلی از تلفیق یالی است. نتیجهٔ تلفیق یال $e=\{u,v\}$ رأس تازهٔ $uv$ خواهد بود. هر یال $\{w,u\}$ یا $\{w,v\}$ برای $w\notin \{u,v\}$ در دو انتهای یال تلفیقی با یک یال $\{w,uv\}$ به رأس تازه جایگزین می‌شود. سرانجام، رئوس تلفیقی $u$ و $v$ با همهٔ یال‌های واقع بر آن حذف می‌شوند. به ویژه گراف حاصل هیچ حلقه‌ای را در بر ندارد. نتیجهٔ تلفیق یال $e$ با $G/e$ نشان داده می‌شود.

الگوریتم تلفیق مرتباً یال‌های تصادفی را در گراف تلفیق می‌کند تا زمانی که فقط دو رأس باقی بماند که آنگاه فقط یک برش یکتا وجود دارد.

اجرای موفق الگوریتم کارگر روی یک گراف ۱۰ رأسی. تعداد یال‌های برشی کمینه ۳ است.

   procedure contract($G=(V,E)$):
   while $|V|>2$
       choose $e\in E$ uniformly at random
       $G\leftarrow G/e$
   return the only cut in $G$

وقتی گراف با استفاده از لیست‌های مجاورت یا ماتریس مجاورت نمایش داده می‌شود، یک عمل یکتای تلفیق یالی را می‌توان با تعدادی بروزرسانی با زمان اجرای خطی روی داده ساختار، با زمان اجرای کل $O(|V|^{2})$، پیاده‌سازی کرد. از سوی دیگر، این روند را می‌توان به منزلهٔ اجرای الگوریتم کروسکال برای ایجاد درخت فراگیر کمینه در گرافی که یال‌هایش بر اساس یک جایگشت تصادفی $\pi$ وزن‌های $w(e_{i})=\pi (i)$ دارند دید. حذف سنگین‌ترین یال این درخت به ایجاد دو مؤلفه می‌انجامد که یک برش را توصیف می‌کنند. به این روش، روند تلفیق را می‌تواند مانند الگوریتم کروسکال در زمان $O(|E|\log |E|)$ پیاده‌سازی کرد.

انتخاب یال‌های تصادفی در الگوریتم کارگر مربوط به اجرای الگوریتم کروسکال روی گرافی با مرتبهٔ یال‌های تصادفی تا زمانی که فقط دو مؤلفه باقی بماند.

بهترین پیاده سازی‌های شناخته شده، به ترتیب از زمان و فضای $O(|E|)$ یا زمان $O(|E|\log |E|)$ و فضای $O(|V|)$ استفاده می‌کنند.

احتمال موفقیت الگوریتم تلفیقی

در گراف $G=(V,E)$ با $n=|V|$ رأس، الگوریتم تلفیقی با احتمال ${\binom {n}{2}}^{-1}$ یک برش کمینه برمی گرداند. در میان $2^{n-1}-1$ برش گراف، حد اکثر ${\binom {n}{2}}$ برش کمینه وجود دارد، بنابراین این احتمال بسیار بهتر از انتخاب یک برش به صورت تصادفی است.

برای مثال، گراف دوری روی $n$ رأس، دقیقاً ${\binom {n}{2}}$ برش کمینه دارد، که از انتخاب هر دو یال به دست می‌آید. روند تلفیق با احتمال برابر هر یک از این یال‌ها را می‌یابد.

برای آن که کران احتمال موفقیت را به‌طور کلی به دست آوریم، اگر یال‌های یک برش کمینهٔ خاص با اندازهٔ $k$ را با $C$ نشان دهیم آنگاه الگوریتم تلفیق $C$ را برمی گرداند اگر و فقط اگر هیچ یک از یال‌های تصادفی در مجموعهٔ برش $C$ نباشد. به ویژه، اولین تلفیق یالی از $C$ اجتناب می‌کند، که با احتمال $1-k/|E|$ رخ می‌دهد. درجهٔ کمینهٔ $G$ حد اقل $k$ است (در غیر این صورت یک رأس با درجهٔ کمینه یک برش کوچک تر را سبب می‌شد)، بنابراین $|E|\geq nk/2$. پس احتمال این که الگوریتم تلفیق، یالی از $C$ را برگزیند برابر است با: ${\frac {k}{|E|}}\leq {\frac {k}{nk/2}}={\frac {2}{n}}$.

احتمال $p_{n}$ که الگوریتم تلفیق روی یک گراف $n$ رأسی از $C$ اجتناب کند، در رابطهٔ بازگشتی $p_{n}\geq {\bigl (}1-{\frac {2}{n}}{\bigr )}p_{n-1}$ با $p_{2}=1$ صدق می‌کند که می‌توان آن را به صورت زیر بسط داد:

$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}\,.$

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

۱۰بار تکرار الگوریتم تلفیق. در پنجمین تکرار، الگوریتم برش کمینه را با اندازهٔ ۳ پیدا می‌کند.

با تکرار $T={\binom {n}{2}}\ln n$ بار الگوریتم تلفیق با انتخاب‌های مستقل تصادفی و برگرداندن کوچک‌ترین برش، احتمال پیدا نکردن برش کمینه عبارتست از: ${\Bigl [}1-{\binom {n}{2}}^{-1}{\Bigr ]}^{T}\leq {\frac {1}{e^{\ln n}}}={\frac {1}{n}}\,.$

زمان اجرای کل برای $T$ بار تکرار برای گرافی با $n$ رأس و $m$ یال برابر است با: $O(Tm)=O(n^{2}m\log n)$.

الگوریتم کارگر_اشتاین

یک بسط الگوریتم کارگر، توسط دیوید کارگر و کلیفورد اشتاین (به انگلیسی: Clifford Stein) به بهبود مرتبهٔ زمانی حالت قبل منجر می‌شود. ایدهٔ اصلی این است که رویهٔ تلفیق تا زمانی که گراف به $t$ رأس برسد انجام شود.

   procedure contract($G=(V,E)$, $t$):
   while $|V|>t$
       choose $e\in E$ uniformly at random
       $G\leftarrow G/e$
   return $G$

احتمال $p_{n,t}$ که این رویهٔ تلفیق از یک برش خاص $C$ در یک گراف $n$ رأسی اجتناب کند چنین است:

${\begin{aligned}p_{n,t}&\geq \prod _{i=0}^{n-t-1}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}={\binom {t}{2}}{\bigg /}{\binom {n}{2}}\,.\end{aligned}}$

این عبارت از $\Omega (t^{2}/n^{2})$ است و از ${\frac {1}{2}}$ حول $t=\lceil 1+n/{\sqrt {2}}\rceil$ کمتر می‌شود. به ویژه احتمال این که یک یال از $C$ تلفیق شود تا پایان افزایش می‌یابد. این انگیزهٔ ایدهٔ تغییر به یک الگوریتم کندتر پس از تعداد معینی گام‌های تلفیقی است.

   procedure fastmincut($G=(V,E)$):
   if $|V|<6$:
       return mincut($V$)
   else:
       $t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil$
       $G_{1}\leftarrow$ contract($G$, $t$)
       $G_{2}\leftarrow$ contract($G$, $t$)
       return min {fastmincut($G_{1}$), fastmincut($G_{2}$)}

تجزیه و تحلیل

احتمال $P(n)$ را احتمال پیدا کردن یک مجموعهٔ برش خاص $C$ توسط الگوریتم در نظر بگیریم آنگاه $P(n)$ با رابطهٔ بازگشتی زیر داده می‌شود:

$P(n)=1-\left(1-{\frac {1}{2}}P\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)\right)^{2}$

که راه حل آن $P(n)=O\left({\frac {1}{\log n}}\right)$ است. زمان اجرای سریع‌ترین برش کمینه در $T(n)=2T\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)+O(n^{2})$

در راه حل $T(n)=O(n^{2}\log n)$ صدق می‌کند.

برای رسیدن به احتمال خطای $O(1/n)$، الگوریتم می‌تواند $O(\log n/P(n))$ بار تکرار گردد، با زمان اجرای کل $T(n)\cdot {\frac {1}{P(n)}}=O(n^{2}\log ^{3}n)$ این یک مرتبهٔ زمانی با بهبود زیاد روی الگوریتم اصلی کارگر است.

یافتن همهٔ برش‌های کمینه

قضیه: با احتمال زیادی می‌توان همهٔ برش‌های کمینه را در زمان اجرای $O(n^{2}\ln ^{3}n)$ یافت.

اثبات: از آنجا که می دانیم $P(n)=O\left({\frac {1}{\ln n}}\right)$، بنابراین پس از اجرای این الگوریتم به تعداد $O(\ln ^{2}n)$ بار، احتمال از بین رفتن یک برش کمینهٔ خاص چنین است:

$\Pr[{\text{miss a specific min-cut}}]=(1-P(n))^{O(\ln ^{2}n)}\leq \left(1-{\frac {c}{\ln n}}\right)^{\frac {3\ln ^{2}n}{c}}\leq e^{-3\ln n}={\frac {1}{n^{3}}}$.

و حداکثر ${\binom {n}{2}}$ برش کمینه وجود دارد، بنابراین احتمال از دست دادن هر برش کمینه چنین است:

$\Pr[{\text{miss any min-cut}}]\leq {\binom {n}{2}}\cdot {\frac {1}{n^{3}}}=O\left({\frac {1}{n}}\right).$

وقتی n به اندازهٔ کافی بزرگ باشد، احتمال شکست به نحو قابل ملاحظه‌ای کم خواهد بود. ∎

کران بهبود

برای تعیین برش کمینه، باید از هر یال در گراف حداقل یک بار بگذریم، که در یک گراف چگال از $O(n^{2})$ است. الگوریتم برش کمینهٔ کارگر_اشتاین زمان اجرای $O(n^{2}\ln ^{O(1)}n)$ می‌برد، که خیلی به آن نزدیک است.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Karger's algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۱ ژوئن ۲۰۱۳.