Kargerin algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28.5.2022 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Kargerin algoritmi
Kaavio ja sen kaksi leikkausta. Punainen leikkaus ylittää kolme reunaa ja vihreä leikkaus kaksi. Jälkimmäinen on yksi tämän kaavion pienimmistä leikkauksista.
Nimetty	David Karger [d]
tarkoitus	löytää kaavion pienin leikkaus
Tietorakenne	kaavio
Keskimääräinen aika	$O(Tm)=O(n^{2}m\log n)$
Muistin hinta	-

Kargerin algoritmi tietojenkäsittelytieteessä ja graafiteoriassa on todennäköisyyspohjainen algoritmi , jonka avulla voit löytää yhdistetyn graafin minimileikkauksen . David Kargerin keksimä algoritmi ja julkaistiin vuonna 1993 [1] .

Algoritmin idea perustuu reunan supistumiseen suuntaamattomassa graafissa. Reunan supistuksen aikana kaksi kärkeä yhdistetään yhdeksi, mikä vähentää graafin kärkien määrää yhdellä. Kaikki supistuneiden kärkien reunat yhdistetään äskettäin muodostettuun kärkipisteeseen, jolloin syntyy multigrafi . Kargerin algoritmi valitsee iteratiivisesti satunnaiset reunat ja suorittaa toiminnon, kunnes jäljellä on kaksi kärkeä, jotka ovat alkuperäisen graafin leikkaus. Jos algoritmia toistetaan tarpeeksi monta kertaa, niin minimileikkaus löytyy suurella todennäköisyydellä.

Kuvaus

Esimerkkejä

Päätehtävänä on löytää pullonkauloja eri verkostoista. Esimerkkejä:

Yhteisöjen löytäminen sosiaalisissa verkostoissa [2] .
Potentiaalisen vihollisen haavoittuvuuksien määrittäminen sen kuljetusverkoston tuhoamiseksi .
Kuvan segmentointi [3] [4] .

Algoritmi

Kargerin algoritmin perustoiminto on eräänlainen reunan supistaminen . Tämän toiminnon suorittamiseksi mielivaltaiselle reunalle graafin ja pisteet yhdistetään yhdeksi . Jos kärkipiste poistetaan , jokainen näkymän reuna korvataan näkymän reunalla . Silmukat poistetaan, ja tämän toimenpiteen jälkeen graafi ei sisällä silmukoita. Kustannusfunktio määritellään uudelleen seuraavasti: . $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)\in E\\c(e)+c((x,v)),&e=(x, u)\land (x,v)\in E\end{cases}}$

Algoritmi on satunnaisen käytettävissä olevan reunan ja kärkien liiton ekvitodennäköinen valinta kuvatun operaation mukaisesti. Algoritmin tuloksena saadaan pistepari, jonka välissä oleva reunajoukko on graafin osa. Tämä leikkaus ei välttämättä ole minimaalinen, mutta todennäköisyys, että tämä leikkaus on minimaalinen, on huomattavasti suurempi kuin satunnaisesti valitulla leikkauksella.

Pseudokoodi

Kargerin algoritmi toista n − 2 kertaa satunnaisesti valitse reuna e kutista reuna e tuloksena on reunojen lukumäärä kahden viimeisen kärjen välillä

Todisteet

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

Todiste. Huomaa, että jokainen leikkaus vastaa leikkausta . Anna , ja . Tällöin seuraavat erot ovat voimassa: , (edellyttäen, että ) ja . Siten . ${\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. Todennäköisyys, että algoritmin tulos on pienin leikkaus, on suurempi tai yhtä suuri kuin . ${\tbinom {n}{2}}^{-1}$

Todiste. Antaa olla -th supistuneen reunan edellyttäen, että . Olkoon ja lisäksi -:nnen supistuksen jälkeiset kaaviot ja mikä tahansa kuvaajan pienin leikkaus . Sitten seuraava on totta: $e_{i}$ $i$ $1\leqslant i\leqslant n-2$ $H_{0}=G$ $Hei$ $i$ $K$ $G$

{\begin{aligned}\mathbb {Pr} [C{\text{ on min.  Leikkaa}}]&\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-algoritmi

Huomaa, että todennäköisyys, että pienintä leikkausta ei löydy toistoista, on . Siten on mahdollista mielivaltaisesti pienentää virheen todennäköisyyttä, mutta tämä pidentää algoritmin suoritusaikaa. Virheen todennäköisyysvakiolle riittää, että algoritmi suoritetaan kerran ja suoritusaika kasvaa arvoon . Kun vakiovirhetodennäköisyys on saavutettu, se pienenee eksponentiaalisesti funktiona . Toistaiseksi mahdolliset pienimmät leikkaukset on generoinut algoritmilla itsenäisesti kussakin kutsussa, mutta ensimmäisten reunaliitosten tuloksia voidaan käyttää useisiin ajoihin. Karger-Stein-algoritmin ideana on tunnistaa kussakin iteraatiossa kaksi supistusehdokasta ja jatkaa Karger-algoritmia rekursiivisesti jokaiselle niistä: $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 ja . $G=(V,E)$ ${\displaystyle c\colon E\to \mathbb {N} ^{+))$
Jos , etsi pienin leikkaus ja tulosta se, lopeta työ. $|V|\leqslant 6$ $C_{U}$
Asenna . $t=\lceil 1+{\frac {n}{\sqrt {2))}\rceil$
Asenna . $H=H'=G$
Vedä kylkiluut sisään . $nt$ $H$
Vedä kylkiluut sisään . $nt$ $H'$
Laske rekusiivisesti pienimmät leikkaukset ja . $C_{H}$ $C_{H'}$
Tulosta pienin leikkaus tai . $C_{H}$ $C_{H'}$

Lause. Karger-Stein-algoritmilla on aika monimutkaisuus . $O(n^{2}\cdot \log n)$

Todiste. Seuraava yksinkertaistettu rekursiivinen yhtälö kuvaa algoritmin ajoaikaa: for ja for . Rekursion syvyys on , koska syöttödatan kokoa pienennetään vakiomäärä kertoja. Olkoon rekursion tasolla . Huomaa, että rekursiotasolla algoritmi on suoritettava kerran ja kunkin rekursiivisen kutsun syötekaavion koko on . Siten jokaisen rekursiivisen kutsun suoritusaika on , ja rekursisyvyyden sisällä vaadittava suoritusaika on . Kokonaissuoritusaika on . $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))$

Todiste.

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

Lause. Algoritmi laskee pienimmän leikkauksen todennäköisyydellä . $\Omega (1/\log n)$

Todiste. Antaa olla pienin leikkaus kaaviossa ja . Silloin todennäköisyys, että se säilyy supistuksen jälkeen, on yhtä suuri kuin minimi: $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}}

Todennäköisyys, että tai joilla on sama pienin leikkaus kuin ja on vähintään . Karger-Stein-algoritmi onnistuu vain kahdessa tapauksessa: jos tai sisältää minimikokoleikkauksen ja algoritmin rekusiivinen kutsu onnistuu. Olkoon todennäköisyys, että algoritmi on onnistunut kuvaajalle . Silloin todennäköisyys, että algoritmi valmistuu onnistuneesti, on . Olkoon todennäköisyys, että algoritmi on onnistunut rekursiotasolla . Sitten todellakin jos ja . Tästä seuraa, että missä on rekursion syvyys. $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)$