Kargers algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. maj 2022; checks kræver 3 redigeringer .

Kargers algoritme
Grafen og dens to snit. Det røde snit krydser tre kanter, og det grønne snit to. Sidstnævnte er en af de minimale udskæringer i denne graf.
Opkaldt efter	David Karger [d]
formål	at finde det mindste snit af en graf
Datastruktur	kurve
Gennemsnitlig tid	$O(Tm)=O(n^{2}m\log n)$
Hukommelsesomkostninger	-

Kargers algoritme inden for datalogi og grafteori er en sandsynlighedsalgoritme , der giver dig mulighed for at finde minimumsskæringen af en forbundet graf . Algoritme opfundet af David Karger og udgivet i 1993 [1] .

Ideen med algoritmen er baseret på kantkontraktion i en urettet graf. Under kantkontraktion slås to hjørner sammen til én, hvilket reducerer antallet af grafhjørner med en. Alle kanter af de sammentrukne toppunkter er forbundet med det nydannede toppunkt, hvilket genererer en multigraf . Kargers algoritme udvælger iterativt tilfældige kanter og udfører operationen, indtil der er to hjørner tilbage, som er et snit af den originale graf. Hvis algoritmen gentages nok gange, kan minimumsskæringen findes med stor sandsynlighed.

Beskrivelse

Eksempler

Hovedopgaven er at finde flaskehalse i forskellige netværk. Eksempler:

Opdagelse af fællesskaber i sociale netværk [2] .
Bestemmelse af sårbarheder hos en potentiel modstander for at ødelægge dens transportnetværk .
Billedsegmentering [3] [4] .

Algoritme

Den grundlæggende operation af Kargers algoritme er en form for kantkontraktion . For at udføre denne operation på en vilkårlig kant , flettes hjørnerne af grafen og sammen til én . Hvis et toppunkt fjernes , erstattes hver visningskant af en visningskant . Sløjferne fjernes, og efter denne operation indeholder grafen ingen løkker. Omkostningsfunktionen omdefineres som følger: . $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)\i E\\c(e)+c((x,v)),&e=(x, u)\land (x,v)\i E\end{cases}}$

Algoritmen er et lige sandsynligt valg af en tilfældig tilgængelig kant og en forening af hjørner i henhold til den beskrevne operation. Resultatet af algoritmen er et par knudepunkter, hvorimellem sættet af kanter er et udsnit af grafen. Dette snit er måske ikke minimalt, men sandsynligheden for, at dette snit er minimalt, er betydeligt større end for et tilfældigt udvalgt snit.

Pseudokode

Kargers algoritme gentag n − 2 gange tilfældigt vælg kant e krympe kant e resultat antal kanter mellem de sidste to hjørner

Beviser

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. Bemærk, at hvert snit svarer til et snit i . Lad , og . Så er følgende forskelle gyldige: , (forudsat at ) og . Således . ${\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. Sandsynligheden for, at resultatet af algoritmen er det mindste snit, er større end eller lig med . ${\tbinom {n}{2}}^{-1}$

Bevis. Lad være den -te kontraheret kant forudsat at . Yderligere, lad og være graferne efter den -. kontraktion, og vær ethvert mindste snit af grafen . Så er følgende sandt: $e_{i}$ $jeg$ $1\leqslant i\leqslant n-2$ $H_{0}=G$ $Hej$ $jeg$ $K$ $G$

{\begin{aligned}\mathbb {Pr} [C{\text{ er min.  Klip}}]&\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{justeret}}

Karger-Stein algoritme

Bemærk, at sandsynligheden for ikke at finde det mindste snit med gentagelser er . Det er således muligt vilkårligt at reducere sandsynligheden for en fejl, men dette vil øge algoritmens eksekveringstid. For fejlsandsynlighedskonstanten er det nok at køre algoritmen én gang, og udførelsestiden vil stige til . Når den konstante fejlsandsynlighed er nået, vil den falde eksponentielt som funktion af . Indtil videre er de mulige mindste snit blevet genereret af algoritmen uafhængigt af hvert kald, men resultaterne af de første kantfletninger kan bruges til mange kørsler. Ideen med Karger-Stein-algoritmen er at identificere to kontraktionskandidater hver iteration og fortsætte Karger-algoritmen rekursivt for hver af 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 og . $G=(V,E)$ ${\displaystyle c\colon E\to \mathbb {N} ^{+))$
Hvis du finder det mindste snit og udskriv det, skal du afslutte jobbet. $|V|\leqslant 6$ $C_{U}$
Installer . $t=\lceil 1+{\frac {n}{\sqrt {2))}\rceil$
Installer . $H=H'=G$
Træk ribbenene ind . $nt$ $H$
Træk ribbenene ind . $nt$ $H'$
Beregn rekusivt de mindste snit og . $C_{H}$ $C_{H'}$
Udskriv det mindste snit eller . $C_{H}$ $C_{H'}$

Sætning. Karger-Stein-algoritmen har tidskompleksitet . $O(n^{2}\cdot \log n)$

Bevis. Følgende forenklede rekursive ligning beskriver køretiden for algoritmen: for og for . Rekursionsdybden er , da størrelsen af inputdata reduceres med et konstant antal gange. Lad på niveauet af rekursion . Bemærk, at på rekursionsniveau er det nødvendigt at køre algoritmen én gang, og størrelsen på inputgrafen for hvert rekursivt kald er . Således er eksekveringstiden for hvert rekursivt opkald , og den nødvendige eksekveringstid inden for rekursionsdybden er . Den samlede udførelsestid er . $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}}

Sætning. Algoritmen beregner det mindste snit med sandsynlighed . $\Omega (1/\log n)$

Bevis. Lad være det mindste snit i grafen og . Så er sandsynligheden for, at den vil blive bevaret efter sammentrækninger lig 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}}

Sandsynligheden for at eller har samme mindste snit som og er mindst . Karger-Stein-algoritmen vil kun lykkes i to tilfælde: hvis eller indeholder en minimumsstørrelse, og det rekusive kald af algoritmen er vellykket. Lad sandsynligheden for, at algoritmen er vellykket for grafen . Så er sandsynligheden for, at algoritmen vil fuldføre med succes . Lad være sandsynligheden for, at algoritmen er vellykket på rekursionsniveauet . Så faktisk hvis og . Det følger heraf , hvor er rekursionsdybden. $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)$