Каргеров алгоритам

У информатици и теорији графова, Каргеров алгоритам је алгоритам насумичне методе који одређује минималан рез повезаног графа. Измислио га је Дејвид Каргер и први пут објавио 1993.^[1]

Идеја алгоритма је базирана на концепту скраћивања грана $(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$ .

Рез се понекад назива и “глобални рез” како би се разликовао од “ $s$ - $t$ реза” за дати пар темена, који има и додатни захтев(услов) да $s\in S$ и $t\in T$ . Сваки глобални рез је $s$ - $t$ рез за неке $s,t\in V$ . Према томе, проблем минималног реза мозе бити решен у полиномијалном времену тако што ћемо да итеришемо(означимо) све случајеве $s,t\in V$ и решавајући резултујући минимум $s$ - $t$ проблема реза користећи теорему о максималном протоку-минималном резу и алгоритам полиномијалног времена за максимални проток, као што је Форд-Фулкерсонов алгоритам, иако овај приступ није препоручљив (оптималан). Постоји детерминистички алгоритам за глобални проблем минималног реза који се извршава у времену $O(mn+n^{2}\log n)$ .^[2]

Алгоритам скраћивања

Фундаментална операција Каргеровог алгоритма је форма скраћивања броја грана. Резултат скраћивања гране $e=\{u,v\}$ је нови чвор $uv$ . Свака грана $\{w,u\}$ или $\{w,v\}$ за $w\notin \{u,v\}$ до крајњих тачака скраћене гране је замењена граном $\{w,uv\}$ до новог чвора. Коначно, скраћени чворови $u$ и $v$ са свим својим старим гранама су уклоњени. Резултујући граф не садржи петље. Резултат скраћене гране $e$ се означава као $G/e$ .

Алгоритам скраћивања изнова и изнова смањује насумично изабране гране графа све док не остану само два чвора, а у том тренутку постоји само један рез.

Успешан пролазак кроз граф са 10 чворова користећи Каргеровог алгоритам. Минималан број резова је 3.

   procedura skraćivanje( $G=(V,E)$ ):
   dok  $|V|>2$ 
       izaberi  $e\in E$  nasumično ravnomerno
        $G\leftarrow G/e$ 
   vrati jedini rez iz  $G$

Када је граф представљен листом суседства или матрицом повезаности, операција скраћивања једне гране може бити имплементирана линеарним бројем ажурирања главне структуре, уз укупно време извршавања $O(|V|^{2})$ . Алтернативно, процедура може бити прегледана уз помоћ Крускаловог алгоритма за констурисање минималног разапињућег стабла где су гране тежине $w(e_{i})=\pi (i)$ на основу насумичне пермутације $\pi$ . Уклањањем најтеже гране овог стабла се добијају две компоненте које описују рез. На овај начин, процедура скраћивања може бити имплементирана уз помоћ Крускаловог алгоритма у времену $O(|E|\log |E|)$ .

Избори насумичних грана уз помоћ Каргеровог алгоритму кореспондира са извршавањем Крускаловог алгоритма у графу са гранама насумичног ранга све док не остану само две компоненте.

Најбоља позната имплементација је $O(|E|)$ временске и просторне сложености, или у $O(|E|\log |E|)$ времену и $O(|V|)$ простору.^[1]

Вероватноћа успешности алгоритма за скраћивање

У графу $G=(V,E)$ са $n=|V|$ чворова, алгоритам скраћивања враћа минималан рез са полиномијално малом вероватноћом ${\binom {n}{2}}^{-1}$ . Сваки граф има $2^{n-1}-1$ резова,^[3] међу којима највише може бити ${\tbinom {n}{2}}$ минималних резова. Стога, вероватноћа успешности овог алгоритма је много боља од вероватноће одабирања реза насумично, што је највише ${\tbinom {n}{2}}/(2^{n-1}-1)$

На пример, циклични граф са $n$ чворова има тачно ${\binom {n}{2}}$ минималних резова, гледавши на сваки избор од по 2 гране. Процедура скраћивања налази сваку од наведених са једнаком вероватноћом.

Како би генерално поставили вероватноћу успешности, нека $C$ буде ознака за ивице одредјеног минималног реза величине $k$ . Алгоритам скраћивања враћа $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}\,.

Понављање алгоритма скраћивања

10 понављања процедуре скраћивања. Пето понављање налази минилани рез величине 3.

Понављањем алгоритма скраћивања $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)$ .

Каргер-Штајнов алгоритам

Наставак (продужетак) Каргеровог алгоритма услед David Karger и Clifford Stein достиже унапређење за ниво више.^[4]

Основна идеја је да се извршава процедура скраћивања све док граф не достигне $t$ чворова.

   procedura skraćivanje( $G=(V,E)$ ,  $t$ ):
   dok  $|V|>t$ 
       izaberi $e\in E$  nasumično ravnomerno
        $G\leftarrow G/e$ 
   vrati  $G$

Вероватноћа $p_{n,t}$ да ова процедура скраћивања избегне одређен рез $C$ у $n$ -чворном графу је

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

Овај израз је $\Omega (t^{2}/n^{2})$ и постаје мањи него од ${\frac {1}{2}}$ око $t=\lceil 1+n/{\sqrt {2}}\rceil$ . Вероватноћа да је грана из $C$ скраћена расте како се приближава крају. Ово мотивише идеју пребацивања на спорији алгоритам после одређеног броја скраћивања (корака скраћивања).

   procedura brziminrez( $G=(V,E)$ ):
   ako  $|V|<6$ :
       vrati minrez( $V$ )
   u suprotnom:
        $t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil$ 
        $G_{1}\leftarrow$  skrati( $G$ ,  $t$ )
        $G_{2}\leftarrow$  skrati( $G$ ,  $t$ )
       vrati min {brziminrez( $G_{1}$ ), brziminrez( $G_{2}$ )}

Анализа

Вероватноћа $P(n)$ да ће алгоритам пронаћи одређени исечак $C$ је задата рекурентном релацијом

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 {\log n}{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{neuspelo nalaženje odredjenog min-reza}}]=(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{neuspelo nalaženje bilo kog min-reza}}]\leq {\binom {n}{2}}\cdot {\frac {1}{n^{3}}}=O\left({\frac {1}{n}}\right).

Вероватноћа за неуспех у проналажењу је изузетно мала када је н довољно велико.∎

Побољшање

Како би се одредио минимални рез мора се проћи кроз све гране графа бар једном, што се обавља за у $O(n^{2})$ времену у густом графу. Каргер-Штајнов алгоритам за одређивање минималног реза се извршава у $O(n^{2}\ln ^{O(1)}n)$ времену, што је приближно горе наведеном.

Референце

^ ^а ^б Каргер, Дејвид (1993). „Глобални минимални резови у РНЦ-у и Отхер Последице Једноставног Алгоритма За Минамалне Резове”. Проц. 4тх Аннуал АЦМ-СИАМ Сyмпосиум он Дисцрете Алгоритхмс.
^ Стоер, Мецхтхилд; Wагнер, Франк (1997). „А симпле мин-цут алгоритхм”. Јоурнал оф тхе АЦМ. 44 (4): 585—591. С2ЦИД 15220291. дои:10.1145/263867.263872.
^ Патригнани, Мауризио; Пиззониа, Мауризио (2001), „Тхе цомплеxитy оф тхе матцхинг-цут проблем”, Ур.: Брандстäдт, Андреас; Ле, Ван Банг, Грапх-Тхеоретиц Цонцептс ин Цомпутер Сциенце: 27тх Интернатионал Wорксхоп, WГ 2001, Болтенхаген, Германy, Јуне 14ÔÇô16, 2001, Процеедингс, Лецтуре Нотес ин Цомпутер Сциенце, 2204, Берлин: Спрингер, стр. 284—295, МР 1905640, дои:10.1007/3-540-45477-2_26 .
^ Каргер, Давид Р.; Стеин, Цлиффорд (1996). „А неw аппроацх то тхе минимум цут проблем”. Јоурнал оф тхе АЦМ. 43 (4): 601—640. С2ЦИД 5385337. дои:10.1145/234533.234534.

[karger1993-1] а ^б Каргер, Дејвид (1993). „Глобални минимални резови у РНЦ-у и Отхер Последице Једноставног Алгоритма За Минамалне Резове”. Проц. 4тх Аннуал АЦМ-СИАМ Сyмпосиум он Дисцрете Алгоритхмс.

[simplemincut-2] Стоер, Мецхтхилд; Wагнер, Франк (1997). „А симпле мин-цут алгоритхм”. Јоурнал оф тхе АЦМ. 44 (4): 585—591. С2ЦИД 15220291. дои:10.1145/263867.263872.

[3] Патригнани, Мауризио; Пиззониа, Мауризио (2001), „Тхе цомплеxитy оф тхе матцхинг-цут проблем”, Ур.: Брандстäдт, Андреас; Ле, Ван Банг, Грапх-Тхеоретиц Цонцептс ин Цомпутер Сциенце: 27тх Интернатионал Wорксхоп, WГ 2001, Болтенхаген, Германy, Јуне 14ÔÇô16, 2001, Процеедингс, Лецтуре Нотес ин Цомпутер Сциенце, 2204, Берлин: Спрингер, стр. 284—295, МР 1905640, дои:10.1007/3-540-45477-2_26 .

[faster-4] Каргер, Давид Р.; Стеин, Цлиффорд (1996). „А неw аппроацх то тхе минимум цут проблем”. Јоурнал оф тхе АЦМ. 43 (4): 601—640. С2ЦИД 5385337. дои:10.1145/234533.234534.

[1]

[2]

[3]

[4]