Produs în zig-zag

În teoria graficelor, produsul în zig-zag al graficelor obișnuite (notat ) ia un grafic mare și un grafic mic și creează un grafic aproximativ de dimensiunea graficului mare, dar puterea celui mic. O proprietate importantă a produsului în zig-zag este că, pentru un expandator bun , răspândirea graficului rezultat este doar puțin mai slabă decât răspândirea graficului . $G,H$ $G\circ H$ $G$ $H$ $H$ $G$

În linii mari, produsul în zig-zag înlocuiește fiecare vârf al graficului cu o copie (nor) a graficului și conectează vârfurile făcând un pas mic (zig) în interiorul norului și apoi un pas mare (zag) între cei doi nori, și încă un pas mic în interiorul norului final. $G\circ H$ $G$ $H$

Produsul zigzag a fost introdus de Reingold, Wadhan și Wigderson [1] . Produsul în zig-zag a fost folosit inițial pentru a construi în mod explicit expansoare și extractoare cu grad constant. Mai târziu, produsul zigzag a fost folosit în teoria complexității computaționale pentru a demonstra egalitatea dintre SL și L [2] .

Definiție

Fie un grafic -regular peste c rotație , și fie -regular grafic peste c rotație mapare . $G$ $D$ $[N]$ $\mathrm {Rot} _{G}$ $H$ $d$ $[D]$ $\mathrm {Rot} _{H}$

Un produs în zig -zag este definit ca un grafic -regular peste , a cărui rotație este definită după cum urmează : $G\circ H$ $d^{2)$ $[N]\times [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'))$ .

Proprietăți

Gradul în scădere

Rezultă direct din definiția produsului în zig-zag că graficul este transformat într-un nou grafic -regular. Astfel, dacă este substanțial mai mare decât , produsul în zig-zag scade gradul de . $G$ $d^{2)$ $G$ $H$ $G$

Aproximativ, produsul în zig-zag transformă fiecare vârf al graficului într-un nor de dimensiunea graficului și distribuie arcele fiecărui vârf original către vârfurile norului care l-a înlocuit. $G$ $H$

Conservarea decalajului spectral

Răspândirea unui grafic poate fi măsurată prin decalajul său spectral. O proprietate importantă a produsului în zig-zag este conservarea decalajului spectral . Astfel, dacă expanderul este „destul de bun” (are un decalaj spectral mare), atunci răspândirea produsului în zig-zag este aproape de răspândirea inițială a graficului . $H$ $G$

Formal: definit ca orice graf cu vârf regulat a cărui a doua valoare proprie ca mărime are o valoare absolută de cel puțin . $(N,D,\lambda )$ $D$ $N$ $\lambda$

Fie — și — două grafice, atunci este un grafic , unde . $G_{1}$ $(N_{1},D_{1},\lambda _{1})$ $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})$

Păstrarea conexiunii

Produsul zigzag funcționează separat pentru fiecare componentă conectată a graficului . $G\circ H$ $G$

Formal: să fie date două grafice: — -graf regulat peste și — -graf obișnuit peste . Dacă este o componentă conexă a graficului , atunci , unde este un subgraf al graficului format din vârfuri (adică un grafic peste , care conține toate arcele dintre vârfuri din ). $G$ $D$ $[N]$ $H$ $d$ $[D]$ $S\subseteq [N]$ $G$ $G|_{S}\circ H=G\circ H|_{S\times D)$ $G|_{S}$ $G$ $S$ $S$ $G$ $S$

Aplicații

Construcția expandoarelor de grad constant

În 2002, Omer Reingold, Salil Wadhan și Avi Widgerson [3] au arătat o construcție combinatorie explicită simplă a expansoarelor de grad constant. Construcția se face iterativ și necesită ca bază un expander de grad constant. La fiecare iterație, produsul zigzag este folosit pentru a crea un alt grafic a cărui dimensiune crește, dar gradul și distribuția rămân aceleași. Prin repetarea procesului, pot fi create expandoare arbitrar mari.

Rezolvarea problemei de conectivitate st nedirecționată într-un spațiu de memorie logaritmic

În 2005, Ömer Reingold a introdus un algoritm pentru rezolvarea problemei st-connectivity , folosind un spațiu de memorie logaritmic. Problema este de a verifica dacă există o cale între două vârfuri date ale unui graf nedirecționat. Algoritmul se bazează în mare măsură pe produsul zigzag.

În linii mari, pentru a rezolva problema de conectivitate nedirecționată st într-un spațiu de memorie logaritmic, graficul original este transformat folosind o combinație de produs și un produs în zig-zag într-un grafic obișnuit de grad constant cu un diametru logaritmic. Produsul mărește răspândirea (prin creșterea diametrului) prin creșterea gradului, iar produsul în zigzag este folosit pentru a scădea gradul menținând în același timp răspândirea.

Vezi și

Operații pe grafice

Note

↑ Reingold, Vadhan, Wigderson, 2000 , p. 3-13.
↑ Omer Reingold. Conectivitate nedirecționată în spațiul de jurnal // Jurnalul ACM . - 2008. - T. 55 , nr. 4 . - S. 24 . - doi : 10.1145/1391289.1391291 .
↑ Reingold, Vadhan, Wigderson, 2000 .

Literatură

Omer Reingold, Salil Vadhan, Avi Wigderson. Proc. Cel de- al 41-lea Simpozion IEEE privind Fundamentele Informaticii (FOCS). - 2000. - S. 3-13 . - doi : 10.1109/SFCS.2000.892006 .
Omer Reingold, Luca Trevisan, Salil Vadhan. Proc. Cel de-al 38-lea Simpozion ACM despre Teoria Calculului (STOC) . - 2006. - S. 457-466 . - doi : 10.1145/1132516.1132583 .