Zigzag produkt

I grafteori tager zigzag-produktet af almindelige grafer (betegnet ) en stor graf og en lille graf og skaber en graf, der er omtrent på størrelse med den store graf, men styrken af den lille. En vigtig egenskab ved zigzag-produktet er, at for en god ekspander er spredningen af den resulterende graf kun lidt dårligere end spredningen af grafen . $G,H$ $G\circ H$ $G$ $H$ $H$ $G$

Groft sagt erstatter zigzag-produktet hvert hjørne af grafen med en kopi (sky) af grafen og forbinder hjørnerne ved at tage et lille skridt (zig) inde i skyen, og derefter et stort skridt (zag) mellem de to skyer, og endnu et lille skridt inde i den sidste sky. $G\circ H$ $G$ $H$

Zigzag-produktet blev introduceret af Reingold, Wadhan og Wigderson [1] . Zigzag-produktet blev oprindeligt brugt til eksplicit at konstruere ekspandere og ekstraktorer med konstant grad. Senere blev zigzag-produktet brugt i beregningsmæssig kompleksitetsteori for at bevise ligheden mellem SL og L [2] .

Definition

Lad være en -regulær graf over c rotation , og lad være -regelmæssig graf over c rotation mapping . $G$ $D$ $[N]$ $\mathrm {Rot} _{G}$ $H$ $d$ $[D]$ $\mathrm {Rot} _{H}$

Et zigzag-produkt er defineret som en -regulær graf over , hvis rotation er defineret som følger : $G\circ H$ ${\displaystyle d^{2))$ $[N]\ gange [D]$ $\mathrm {Rot} _{G\circ H}$
$\mathrm {Rot} _{G\circ H}((v,a),(i,j))$

$(a',i')=\mathrm {Rot} _{H}(a,i)$ .
$(w,b')=\mathrm {Rot} _{G}(v,a')$ .
$(b,j')=\mathrm {Rot} _{H}(b',j)$ .
$>\mathrm {Rot} _{G\circ H}((v,a),(i,j))=((w,b),(j',i'))$ .

Egenskaber

Aftagende grad

Det følger direkte af definitionen af zigzag-produktet, at grafen omdannes til en ny -regulær graf. Således, hvis væsentligt større end , reducerer zigzag-produktet graden af . $G$ ${\displaystyle d^{2))$ $G$ $H$ $G$

Groft sagt forvandler zigzag-produktet hvert hjørne af grafen til en sky på størrelse med grafen og fordeler buerne af hvert oprindelige hjørne til hjørnerne af skyen, der erstattede det. $G$ $H$

Bevarelse af spektralgabet

Spredningen af en graf kan måles ved dens spektrale mellemrum. En vigtig egenskab ved zigzag-produktet er bevarelsen af spektralgabet . Hvis ekspanderen således er "god nok" (har et stort spektralgab), så er spredningen af zigzag-produktet tæt på den oprindelige spredning af grafen . $H$ $G$

Formelt: defineret som enhver -regular vertex-graf, hvis næststørste egenværdi har en absolut værdi på mindst . $(N,D,\lambda )$ $D$ $N$ $\lambda$

Lad - og - være to grafer, så er en graf , hvor . ${\displaystyle G_{1))$ $(N_{1},D_{1},\lambda _{1})$ ${\displaystyle G_{2))$ $(D_{1},D_{2},\lambda _{2})$ $G\circ {z}H$ $(N_{1}\cdot D_{1},D_{2}^{2},f(\lambda _{1},\lambda _{2}))$ $f(\lambda _{1},\lambda _{2})<\lambda _{1}+\lambda _{2}+\lambda _{2}^{2})$

Bevarelse af forbundethed

Zigzag-produktet fungerer separat for hver tilsluttet komponent i grafen . $G\circ H$ $G$

Formelt: lad to grafer gives: — -regulær graf over og — -regulær graf over . Hvis er en forbundet komponent af grafen , så , hvor er en undergraf af grafen dannet af hjørner (det vil sige en graf over , der indeholder alle buer fra mellem hjørner fra ). $G$ $D$ $[N]$ $H$ $d$ $[D]$ $S\subseteq [N]$ $G$ ${\displaystyle G|_{S}\cirkel H=G\cirkel H|_{S\ gange D))$ $G|_{S}$ $G$ $S$ $S$ $G$ $S$

Ansøgninger

Konstruktion af ekspandere med konstant grad

I 2002 viste Omer Reingold, Salil Wadhan og Avi Widgerson [3] en simpel eksplicit kombinatorisk konstruktion af konstante gradudvidere. Konstruktionen udføres iterativt og kræver en ekspander af konstant grad som grundlag. Ved hver iteration bruges zigzag-produktet til at skabe en anden graf, hvis størrelse øges, men graden og fordelingen forbliver den samme. Ved at gentage processen kan der skabes vilkårligt store ekspandere.

Løsning af det urettede forbindelsesproblem i et logaritmisk hukommelsesrum

I 2005 introducerede Ömer Reingold en algoritme til løsning af st-forbindelsesproblemet ved at bruge et logaritmisk hukommelsesrum. Problemet er at kontrollere, om der er en sti mellem to givne hjørner af en urettet graf. Algoritmen er stærkt afhængig af zigzag-produktet.

Groft sagt, for at løse det urettede forbindelsesproblem st i et logaritmisk hukommelsesrum, transformeres den originale graf ved hjælp af en kombination af et produkt og et zigzag-produkt til en regulær graf af konstant grad med en logaritmisk diameter. Produktet øger spredningen (ved at øge diameteren) ved at øge graden, og zigzag-produktet bruges til at mindske graden og samtidig bevare spredningen.

Se også

Operationer på grafer

Noter

↑ Reingold, Vadhan, Wigderson, 2000 , s. 3-13.
↑ Omer Reingold. Udirigeret forbindelse i log-space // Journal of the ACM . - 2008. - T. 55 , no. 4 . - S. 24 . - doi : 10.1145/1391289.1391291 .
↑ Reingold, Vadhan, Wigderson, 2000 .

Litteratur

Omer Reingold, Salil Vadhan, Avi Wigderson. Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS). - 2000. - S. 3-13 . - doi : 10.1109/SFCS.2000.892006 .
Omer Reingold, Luca Trevisan, Salil Vadhan. Proc. 38. ACM Symposium on Theory of Computing (STOC) . - 2006. - S. 457-466 . - doi : 10.1145/1132516.1132583 .