Karger algoritmusa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. május 28-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

Karger algoritmusa
A grafikon és két vágása. A piros vágás három élt keresztez, a zöld pedig kettőt. Ez utóbbi ennek a grafikonnak az egyik minimális vágása.
Valaki után elnevezve	David Karger [d]
célja	a grafikon legkisebb metszetének megtalálása
Adatstruktúra	grafikon
Átlagos idő	$O(Tm)=O(n^{2}m\log n)$
A memória költsége	-

Karger algoritmusa a számítástechnikában és a gráfelméletben egy valószínűségi algoritmus , amely lehetővé teszi egy összefüggő gráf minimális metszésének megtalálását . Az algoritmust David Karger találta ki és 1993 -ban jelent meg [1] .

Az algoritmus ötlete egy irányítatlan gráf élösszehúzódásán alapul . Az élösszehúzás során két csúcs összevonódik egybe, ami eggyel csökkenti a gráf csúcsok számát. Az összehúzott csúcsok összes éle kapcsolódik az újonnan kialakított csúcshoz, így multigráfot generál . A Karger-algoritmus iteratív módon kiválasztja a véletlenszerű éleket, és addig hajtja végre a műveletet, amíg két csúcs marad, amelyek az eredeti gráf egy metszete. Ha az algoritmust elégszer megismételjük, akkor a minimális vágás nagy valószínűséggel megtalálható.

Leírás

Példák

A fő feladat a szűk keresztmetszetek megtalálása a különböző hálózatokban. Példák:

Közösségek felfedezése a közösségi hálózatokban [2] .
A potenciális ellenfél sebezhetőségeinek meghatározása annak érdekében, hogy megsemmisítse a szállítási hálózatát .
Képszegmentálás [3] [4] .

Algoritmus

A Karger-algoritmus alapművelete az élösszehúzódás egyik formája . Ahhoz, hogy ezt a műveletet tetszőleges élen hajtsuk végre , a és a gráf csúcsait egyesítjük . Ha egy csúcsot eltávolítunk , akkor minden nézet élét egy nézet él helyettesíti . A ciklusok eltávolításra kerülnek, és a művelet után a gráf nem tartalmaz ciklusokat. A költségfüggvény újradefiniálása a következőképpen történik: . $e=\{u,v\}$ $u$ $v$ $UV$ $v$ ${\displaystyle \{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)\in E\\c(e)+c((x,v)),&e=(x, u)\land (x,v)\in E\end{cases}}$

Az algoritmus egy véletlenszerűen elérhető él és csúcsok uniójának ekvivalens választása a leírt művelet szerint. Az algoritmus eredménye egy csúcspár, amelyek közötti élhalmaz a gráf egy szakasza. Lehet, hogy ez a vágás nem minimális, de annak a valószínűsége, hogy ez a vágás minimális, lényegesen nagyobb, mint egy véletlenszerűen kiválasztott vágásnál.

Pszeudokód

Karger algoritmusa ismétlés n − 2 - szer véletlenszerűen válassza ki az élt e zsugorítja az élt e eredmény az élek száma az utolsó két csúcs között

Bizonyíték

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

Bizonyíték. Vegye figyelembe, hogy minden bevágás egy bevágásnak felel meg . Hagyjuk , és . Ekkor a következő eltérések érvényesek: , (feltéve, hogy ) és . Így . ${\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}}$

2. lemma. Annak a valószínűsége, hogy az algoritmus eredménye a legkisebb vágás, nagyobb vagy egyenlő, mint . ${\tbinom {n}{2}}^{-1}$

Bizonyíték. Legyen a -edik összehúzott él, feltéve, hogy . Továbbá legyen és a -edik összehúzódás utáni grafikonok , és a gráf bármely legkisebb metszete . Akkor a következő igaz: $e_{i}$ $én$ $1\leqslant i\leqslant n-2$ $H_{0}=G$ $Szia$ $én$ $K$ $G$

{\begin{aligned}\mathbb {Pr} [C{\text{ egy min.  Vágás}}]&\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{igazított}}

Karger-Stein algoritmus

Vegye figyelembe, hogy annak a valószínűsége, hogy nem találja meg a legkisebb vágást az ismétlésekkel, . Így tetszőlegesen csökkenthető a hiba valószínűsége, de ez megnöveli az algoritmus végrehajtási idejét. A hibavalószínűségi állandóhoz elég egyszer lefuttatni az algoritmust, és a végrehajtási idő -ra nő . Az állandó hibavalószínűség elérése után exponenciálisan csökken a függvényében . Eddig a lehetséges legkisebb vágásokat az algoritmus külön-külön generálta minden híváson, de az első élösszevonások eredményei számos futtatásra felhasználhatók. A Karger-Stein algoritmus ötlete az, hogy minden iterációban azonosítson két összehúzódási jelöltet, és mindegyiknél rekurzívan folytassa a Karger algoritmust: $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 és . $G=(V,E)$ ${\displaystyle c\colon E\to \mathbb {N} ^{+))$
Ha , keresse meg a legkisebb vágást és adja ki, fejezze be a munkát. $|V|\leqslant 6$ $C_{U}$
Telepítse . $t=\lceil 1+{\frac {n}{\sqrt {2))}\rceil$
Telepítse . $H=H'=G$
Húzza be a bordákat . $nt$ $H$
Húzza be a bordákat . $nt$ $H'$
Számítsa ki rekuszív módon a legkisebb vágásokat és . $C_{H}$ ${\displaystyle C_{H'))$
Adja ki a legkisebb vágást vagy . $C_{H}$ ${\displaystyle C_{H'))$

Tétel. A Karger-Stein algoritmus időben bonyolult . $O(n^{2}\cdot \log n)$

Bizonyíték. Az alábbi egyszerűsített rekurzív egyenlet írja le az algoritmus futási idejét: for and for . A rekurziós mélység , mivel a bemeneti adatok mérete konstans számú alkalommal csökken. Legyen a rekurzió szintjén . Vegye figyelembe, hogy rekurziós szinten az algoritmust egyszer kell futtatni, és minden rekurzív hívás bemeneti gráfjának mérete . Így minden rekurzív hívás végrehajtási ideje , a rekurziós mélységen belül szükséges végrehajtási idő pedig . A teljes végrehajtási idő . $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))$

Bizonyíték.

{\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{igazított}}

Tétel. Az algoritmus kiszámítja a legkisebb vágást valószínűséggel . $\Omega (1/\log n)$

Bizonyíték. Legyen a legkisebb vágás a grafikonon és . Ekkor annak a valószínűsége, hogy az összehúzódások után megmarad , egyenlő a minimummal: $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}}

Annak a valószínűsége, hogy vagy azonos a legkisebb vágással, mint és legalább . A Karger-Stein algoritmus csak két esetben lesz sikeres: ha vagy tartalmaz egy minimális méretű vágást , és az algoritmus rekuszív hívása sikeres. Legyen annak a valószínűsége, hogy az algoritmus sikeres lesz a gráf esetében . Ekkor annak a valószínűsége, hogy az algoritmus sikeresen befejeződik, . Legyen annak a valószínűsége, hogy az algoritmus sikeres lesz a rekurzió szintjén . Akkor valóban , ha és . Ebből következik, hogy hol van a rekurziós mélység. $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)$