Kargers algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 maj 2022; kontroller kräver 3 redigeringar .

Kargers algoritm
Grafen och dess två snitt. Det röda snittet korsar tre kanter och det gröna snittet två. Det senare är en av de minimala snitten i denna graf.
Döpt efter	David Karger [d]
ändamål	hitta det minsta snittet i en graf
Datastruktur	Graf
Snittid	$O(Tm)=O(n^{2}m\log n)$
Minneskostnad	-

Kargers algoritm - inom datavetenskap och grafteori är en probabilistisk algoritm som låter dig hitta minimisnittet för en sammankopplad graf . Algoritm uppfann av David Karger och publicerades 1993 [1] .

Idén med algoritmen är baserad på kantkontraktion i en oriktad graf. Under kantkontraktion slås två hörn samman till en, vilket minskar antalet grafhörn med en. Alla kanter på de sammandragna hörnen är anslutna till den nybildade vertexen, vilket genererar en multigraf . Kargers algoritm väljer iterativt slumpmässiga kanter och utför operationen tills två hörn återstår, som är ett snitt av den ursprungliga grafen. Om algoritmen upprepas tillräckligt många gånger, kan minimisnittet hittas med hög sannolikhet.

Beskrivning

Exempel

Huvuduppgiften är att hitta flaskhalsar i olika nätverk. Exempel:

Upptäckt av samhällen i sociala nätverk [2] .
Att fastställa sårbarheten hos en potentiell motståndare för att förstöra dess transportnätverk .
Bildsegmentering [3] [4] .

Algoritm

Den grundläggande operationen av Kargers algoritm är en form av kantkontraktion . För att utföra den här operationen på en godtycklig kant slås grafens hörn och samman till en . Om en vertex tas bort ersätts varje vykant med en vykant . Slingorna tas bort, och efter denna operation innehåller grafen inga slingor. Kostnadsfunktionen omdefinieras enligt följande: . $e=\{u,v\}$ $u$ $v$ $UV$ $v$ $\{v,x\}$ $\{u,x\}$ $c'(e)={\begin{cases}c(e),&u,v\notin e\\c(e),&e=(x,u)\land (x,v)\notin E \\c((x,v)),&e\neq (x,u)\land (x,v)\i E\\c(e)+c((x,v)),&e=(x, u)\land (x,v)\i E\end{fall}}$

Algoritmen är ett lika sannolikt val av en slumpmässig tillgänglig kant och en förening av hörn enligt den beskrivna operationen. Resultatet av algoritmen är ett par hörn, vars uppsättning kanter är en sektion av grafen. Detta snitt kanske inte är minimalt, men sannolikheten att detta snitt är minimalt är betydligt större än för ett slumpmässigt valt snitt.

Pseudokod

Kargers algoritm upprepa n − 2 gånger slumpmässigt välj kant e krympkant e resultat antal kanter mellan de två sista hörnen

Bevis

Lemma 1. . $\mathbb {Pr} [e_{i}\notin K\mid \bigcap _{1\leqslant j<i}e_{j}\notin K]\geqslant 1-{\frac {2}{n- i+1}}$

Bevis. Observera att varje inskärning motsvarar en inskärning . Låt , och . Då är följande skillnader giltiga: , (förutsatt att ) och . Alltså . ${\displaystyle H_{j))$ $G$ $k=|K|$ $n_{j}=|V(H_{j})|$ $m_{j}=|E(H_{j})|$ $n_{i-1}=n-i+1$ $m_{i-1}\geqslant k\cdot n_{i-1}/2$ $k\leqslant \delta (H_{i-1})$ ${\displaystyle \mathbb {Pr} [e_{i}\in K]={\frac {k}{m_{i-1))))$ $\mathbb {Pr} [e_{i}\notin K\mid \bigcap _{1\leqslant j<i}e_{j}\notin K]={\frac {k}{m_{i-1 ))}\geqslant {\frac {2}{n_{i-1}}}=1-{\frac {2}{n-i+1}}$

Lemma 2. Sannolikheten att resultatet av algoritmen är det minsta snittet är större än eller lika med . ${\tbinom {n}{2}}^{-1}$

Bevis. Låt vara den -: e sammandragna kanten förutsatt att . Vidare, låt och vara graferna efter den -e sammandragningen, och vara vilket minsta snitt av grafen som helst . Då är följande sant: $e_{i}$ $i$ $1\leqslant i\leqslant n-2$ $H_{0}=G$ $Hej$ $i$ $K$ $G$

{\begin{aligned}\mathbb {Pr} [C{\text{ är en min.  Cut}}]&\geqslant \mathbb {Pr} [C=K]\\&=\mathbb {Pr} [\bigcap _{1\leqslant i\leqslant n-2}e_{i}\notin K]\ \&=\prod _{1\leqslant i\leqslant n-2}\mathbb {Pr} [e_{i}\notin K\mid \bigcap _{1\leqslant j<i}e_{j}\notin K ]\\&\geqslant \prod _{1\leqslant i\leqslant n-2}(1-{\frac {2}{n-i+1)))\\&=\prod _{1\leqslant i \leqslant n-2}{\frac {ni-1}{n-i+1}}\\&={\frac {n-2}{n}}\cdot {\frac {n-3}{n -1}}\cdot \dots \cdot {\frac {2}{4}}\cdot {\frac {1}{3}}\\&={\frac {2}{n(n-1)} }={\tbinom {n}{2}}^{-1}\\\end{aligned}}

Karger-Stein algoritm

Observera att sannolikheten för att inte hitta det minsta snittet med upprepningar är . Således är det möjligt att godtyckligt minska sannolikheten för ett fel, men detta kommer att öka exekveringstiden för algoritmen. För felsannolikhetskonstanten räcker det att köra algoritmen en gång och exekveringstiden ökar till . När den konstanta felsannolikheten har uppnåtts kommer den att minska exponentiellt som en funktion av . Hittills har de möjliga minsta nedskärningarna genererats av algoritmen oberoende av varje anrop, men resultaten från de första kantsammanslagningarna kan användas för många körningar. Tanken med Karger-Stein-algoritmen är att identifiera två kontraktionskandidater varje iteration och fortsätta Karger-algoritmen rekursivt för var och en av dem: $t\cdot {\tbinom {n}{2))$ $(1-{\tbinom {n}{2}}^{-1})^{t\cdot {\tbinom {n}{2}}}\leqslant (1/e)^{t}$ ${\tbinom {n}{2))$ $O(n^{4})$ $t$

Dana och . $G=(V,E)$ ${\displaystyle c\colon E\to \mathbb {N} ^{+))$
Om , hitta det minsta snittet och mata ut det, avsluta jobbet. $|V|\leqslant 6$ $C_{U}$
Installera . $t=\lceil 1+{\frac {n}{\sqrt {2))}\rceil$
Installera . $H=H'=G$
Dra revbenen i . $nt$ $H$
Dra revbenen i . $nt$ $H'$
Beräkna rekusivt de minsta snitten och . $C_{H}$ ${\displaystyle C_{H'))$
Mata ut det minsta snittet eller . $C_{H}$ ${\displaystyle C_{H'))$

Sats. Karger-Stein-algoritmen har tidskomplexitet . $O(n^{2}\cdot \log n)$

Bevis. Följande förenklade rekursiva ekvation beskriver körtiden för algoritmen: för och för . Rekursionsdjupet är , eftersom storleken på indata minskas med ett konstant antal gånger. Låt på nivån av rekursion . Observera att på rekursionsnivån är det nödvändigt att köra algoritmen en gång och storleken på indatagrafen för varje rekursivt anrop är . Sålunda är exekveringstiden för varje rekursivt anrop , och exekveringstiden som krävs inom rekursionsdjupet är . Den totala exekveringstiden är . $T(n)=2\cdot T(\lceil 1+{\frac {n}{\sqrt {2}}}\rceil )+O(n^{2})$ $n>6$ $T(n)=O(1)$ $n\leqslant 6$ $D=O(\log n)$ $n_{l}=|V(H)|$ $l\geqslant 0$ $l$ $2^l$ ${\displaystyle n_{l}\equiv {\frac {n}{({\sqrt {2)))^{l))))$ $O(n_{l}^{2})=O({\frac {n^{2}}{2^{l}}})$ $2^{l}\cdot O({\frac {n^{2}}{2^{l}}})=O(n^{2})$ $O(n^{2}\cdot \log n)$

Lemma. . $p(t)\geqslant {\frac {1}{t+1))$

Bevis.

{\begin{aligned}p(t)&\geqslant 1-(1-p(t-1)/2)^{2}\\&\geqslant 1-(1-{\frac {1} {2t)))^{2}\\&={\frac {1}{t}}-{\frac {1}{4t^{2}}}\\&={\frac {4t-1} {4t^{2}}}\\&={\frac {(4t-1)(t+1)}{4t^{2}}}\cdot {\frac {1}{t+1}}\ \&={\frac {4t^{2}+4t-t-1}{4t^{2}}}\cdot {\frac {1}{t+1}}\\&\geqslant {\frac { 1}{t+1}}\end{aligned}}

Sats. Algoritmen beräknar det minsta snittet med sannolikhet . $\Omega (1/\log n)$

Bevis. Låta vara det minsta snittet i grafen och . Då är sannolikheten att den kommer att bevaras efter sammandragningar lika med minimum: $K$ $k=|K|$ $K$ $nt$

{\begin{aligned}\prod _{1\leqslant i\leqslant nt}(1-{\frac {2}{n-i+1)))&=\prod _{1\leqslant i\ leqslant nt}({\frac {ni-1}{n-i+1)))\\&={\frac {n-2}{n}}\cdot {\frac {n-3}{n- 1}}\cdot \dots \cdot {\frac {t}{t+2}}\cdot {\frac {t-1}{t+1}}\\&={\frac {t(t-1 )) )}{n(n-1)))\\&={\frac {\lceil 1+n/{\sqrt {2))\rceil \cdot \lceil n/{\sqrt {2))\ rceil } {n(n-1)}}\\&\geqslant {\frac {1}{2}}\\\end{aligned}}

Sannolikheten att eller har samma minsta snitt som och är minst . Karger-Stein-algoritmen kommer endast att lyckas i två fall: om eller innehålla en minimistorlek , och det återkommande anropet av algoritmen lyckas. Låt sannolikheten att algoritmen är framgångsrik för grafen . Då är sannolikheten att algoritmen kommer att slutföras framgångsrikt . Låt vara sannolikheten att algoritmen är framgångsrik på rekursionsnivån . Då verkligen om och . Det följer att , var är rekursionsdjupet. $H$ $H'$ $G$ ${\frac {1}{2))$ $H$ $H'$ $k$ $P(G')$ $G'$ $P(G)\geqslant 1-(1-P(H)/2)\cdot (1-P(H')/2)$ $p(t)$ $t$ ${\displaystyle p(t)\geqslant 1-(1-p(t-1)/2)^{2))$ $t\geqslant 1$ $p(0)=1$ $p(t)\geqslant {\frac {1}{t+1))$ $P(G)=p(D)\geqslant {\frac {1}{D+1}}=\Omega ({\frac {1}{\log n)))$ $D=O(\log n)$