Kargerův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. května 2022; kontroly vyžadují 3 úpravy .

Kargerův algoritmus
Graf a jeho dva řezy. Červený řez překračuje tři okraje a zelený řez dva. Ten je jedním z minimálních řezů tohoto grafu.
Pojmenoval podle	David Karger [d]
účel	nalezení nejmenšího řezu grafu
Datová struktura	graf
Průměrný čas	$O(Tm)=O(n^{2}m\log n)$
Náklady na paměť	-

Kargerův algoritmus - v informatice a teorii grafů je pravděpodobnostní algoritmus , který vám umožňuje najít minimální řez spojeného grafu . Algoritmus vynalezený Davidem Kargerem a publikováno v roce 1993 [1] .

Myšlenka algoritmu je založena na kontrakci hran v neorientovaném grafu. Při kontrakci hrany se dva vrcholy spojí do jednoho, čímž se počet vrcholů grafu sníží o jeden. Všechny hrany kontrahovaných vrcholů jsou spojeny s nově vytvořeným vrcholem a generují multigraf . Kargerův algoritmus iterativně vybírá náhodné hrany a provádí operaci, dokud nezůstanou dva vrcholy, které jsou výřezem z původního grafu. Pokud se algoritmus opakuje dostatečně často, pak lze s vysokou pravděpodobností nalézt minimální řez.

Popis

Příklady

Hlavním úkolem je najít úzká místa v různých sítích. Příklady:

Objevování komunit v sociálních sítích [2] .
Určení zranitelnosti potenciálního protivníka za účelem zničení jeho dopravní sítě .
Segmentace obrazu [3] [4] .

Algoritmus

Základní operací Kargerova algoritmu je forma zkracování hran . Chcete-li provést tuto operaci na libovolné hraně , jsou vrcholy grafu a sloučeny do jednoho . Pokud je vrchol odstraněn , pak je každá hrana pohledu nahrazena hranou pohledu . Smyčky jsou odstraněny a po této operaci graf neobsahuje žádné smyčky. Nákladová funkce je nově definována následovně: . $e=\{u,v\}$ $u$ $proti$ $UV$ $proti$ $\{v,x\}$ ${\displaystyle \{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}}$

Algoritmus je ekvipravděpodobná volba náhodné dostupné hrany a sjednocení vrcholů podle popsané operace. Výsledkem algoritmu je dvojice vrcholů, množina hran mezi nimiž je výřez grafu. Tento řez nemusí být minimální, ale pravděpodobnost, že tento řez je minimální, je výrazně větší než u náhodně vybraného řezu.

Pseudokód

Kargerův algoritmus opakování n − 2x náhodně vybrat hranu e zmenšit hranu e výsledek počet hran mezi posledními dvěma vrcholy

Důkazy

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}}$

Důkaz. Všimněte si, že každý střih odpovídá střihu . Nechte , a . Pak platí tyto rozdíly: , (za předpokladu, že ) a . Tedy . ${\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. Pravděpodobnost, že výsledkem algoritmu je nejmenší řez, je větší nebo rovna . ${\tbinom {n}{2}}^{-1}$

Důkaz. Nechť je -tá stažená hrana za předpokladu, že . Dále nechť a být grafy po -té kontrakci a být jakýmkoli nejmenším řezem grafu . Pak platí následující: $e_{i}$ $i$ $1\leqslant i\leqslant n-2$ $H_{0}=G$ $Ahoj$ $i$ $K$ $G$

{\begin{aligned}\mathbb {Pr} [C{\text{ je 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ův algoritmus

Všimněte si, že pravděpodobnost, že nenajdete nejmenší řez s opakováním, je . Je tedy možné libovolně snížit pravděpodobnost chyby, ale prodlouží se tím doba provádění algoritmu. Pro konstantu pravděpodobnosti chyby stačí spustit algoritmus jednou a doba provádění se prodlouží na . Jakmile je dosaženo konstantní pravděpodobnosti chyby, bude exponenciálně klesat jako funkce . Doposud byly možné nejmenší řezy generovány algoritmem nezávisle na každém volání, ale výsledky sloučení první hrany lze použít pro mnoho běhů. Myšlenkou algoritmu Karger-Stein je identifikovat dva kandidáty na kontrakci v každé iteraci a rekurzivně pokračovat v Kargerově algoritmu pro každého z nich: $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 a . $G=(V,E)$ ${\displaystyle c\colon E\to \mathbb {N} ^{+))$
Pokud najdete nejmenší řez a vytiskněte jej, dokončete práci. $|V|\leqslant 6$ $C_{U}$
Nainstalujte . $t=\lceil 1+{\frac {n}{\sqrt {2))}\rceil$
Nainstalujte . $H=H'=G$
Vytáhněte žebra do . $nt$ $H$
Vytáhněte žebra do . $nt$ $H'$
Vypočítejte rekusivně nejmenší řezy a . $C_{H}$ $C_{H'}$
Výstup nejmenšího řezu nebo . $C_{H}$ $C_{H'}$

Teorém. Algoritmus Karger-Stein má časovou složitost . $O(n^{2}\cdot \log n)$

Důkaz. Následující zjednodušená rekurzivní rovnice popisuje dobu běhu algoritmu: for a for . Hloubka rekurze je , protože velikost vstupních dat je redukována konstantním počtem opakování. Nechť na úrovni rekurze . Všimněte si, že na úrovni rekurze je nutné spustit algoritmus jednou a velikost vstupního grafu pro každé rekurzivní volání je . Doba provedení každého rekurzivního volání je tedy , a doba provedení požadovaná v rámci hloubky rekurze je . Celková doba provedení je . $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))$

Důkaz.

{\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}}

Teorém. Algoritmus vypočítá nejmenší řez s pravděpodobností . $\Omega (1/\log n)$

Důkaz. Dovolit být nejmenší řez v grafu a . Pravděpodobnost, že bude zachována i po kontrakcích, je pak rovna minimu: $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}}

Pravděpodobnost, že nebo bude mít stejný nejmenší řez jako a je alespoň . Algoritmus Karger-Stein uspěje pouze ve dvou případech: pokud nebo obsahuje minimální velikost řezu a rekuzivní volání algoritmu je úspěšné. Nechť pravděpodobnost, že algoritmus je úspěšný pro graf . Pak je pravděpodobnost, že algoritmus bude úspěšně dokončen, . Nechť je pravděpodobnost, že je algoritmus úspěšný na úrovni rekurze . Pak skutečně pokud a . Z toho vyplývá, že , kde je hloubka rekurze. $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)$