Cikcak produkt

V teorii grafů klikatý součin pravidelných grafů (označený ) vezme velký graf a malý graf a vytvoří graf zhruba velikosti velkého grafu, ale mocniny malého. Důležitou vlastností klikatého součinu je, že pro dobrý expandér je rozptyl výsledného grafu jen o málo horší než rozptyl grafu . $G,H$ $G\circ H$ $G$ $H$ $H$ $G$

Zhruba řečeno, klikatý součin nahradí každý vrchol grafu kopií (oblakem) grafu a spojí vrcholy tak, že udělá malý krok (cik-cak) uvnitř oblaku a pak velký krok (zag) mezi dvěma mraky, a další malý krůček uvnitř konečného mraku. $G\circ H$ $G$ $H$

Produkt cikcak zavedli Reingold, Wadhan a Wigderson [1] . Produkt cik-cak byl původně používán k explicitní konstrukci expandérů a extraktorů konstantního stupně. Později byl klikatý součin použit v teorii výpočetní složitosti k prokázání rovnosti SL a L [2] .

Definice

Nechť je a- regular graf přes c rotaci a nechť je -regular graf přes c rotaci mapování . $G$ $D$ $[N]$ $\mathrm {Rot} _{G}$ $H$ $d$ $[D]$ $\mathrm {Rot} _{H}$

Klikatý součin je definován jako -běžný graf přes , jehož rotace je definována následovně : $G\circ H$ ${\displaystyle 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'))$ .

Vlastnosti

Klesající stupeň

Z definice klikatého součinu přímo vyplývá, že se graf transformuje na nový -regulární graf. Je-li tedy podstatně větší než , klikatý součin snižuje stupeň . $G$ ${\displaystyle d^{2))$ $G$ $H$ $G$

Zhruba řečeno, klikatý součin změní každý vrchol grafu na oblak velikosti grafu a rozdělí oblouky každého původního vrcholu do vrcholů oblaku, který jej nahradil. $G$ $H$

Zachování spektrální mezery

Šíření grafu lze měřit jeho spektrální mezerou. Důležitou vlastností klikatého součinu je zachování spektrální mezery . Pokud je tedy expandér „dost dobrý“ (má velkou spektrální mezeru), pak se rozptyl klikatého produktu blíží původnímu rozptylu grafu . $H$ $G$

Formálně: definováno jako libovolný -regulární vrcholový graf, jehož druhá největší vlastní hodnota má absolutní hodnotu alespoň . $(N,D,\lambda )$ $D$ $N$ $\lambda$

Nechť — a — jsou dva grafy, pak je graf , kde . $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})$

Zachování propojenosti

Klikatý součin funguje samostatně pro každou připojenou složku grafu . $G\circ H$ $G$

Formálně: nechť jsou uvedeny dva grafy: — -běžný graf přes a — -běžný graf přes . Jestliže je souvislá složka grafu , pak , kde je podgraf grafu tvořený vrcholy (tedy graf přes , obsahující všechny oblouky mezi vrcholy od ). $G$ $D$ $[N]$ $H$ $d$ $[D]$ $S\subseteq [N]$ $G$ ${\displaystyle G|_{S}\circ H=G\circ H|_{S\times D))$ $G|_{S}$ $G$ $S$ $S$ $G$ $S$

Aplikace

Konstrukce expandérů konstantního stupně

V roce 2002 ukázali Omer Reingold, Salil Wadhan a Avi Widgerson [3] jednoduchou explicitní kombinatorickou konstrukci expandérů konstantního stupně. Konstrukce se provádí iterativně a jako základ vyžaduje expandér konstantního stupně. Při každé iteraci se klikatý součin používá k vytvoření dalšího grafu, jehož velikost se zvětšuje, ale stupeň a distribuce zůstávají stejné. Opakováním procesu lze vytvořit libovolně velké expandéry.

Řešení problému s neorientovanou konektivitou v logaritmickém paměťovém prostoru

V roce 2005 představil Ömer Reingold algoritmus pro řešení problému st-konektivity pomocí logaritmického paměťového prostoru. Problém je ověřit, zda mezi dvěma danými vrcholy neorientovaného grafu existuje cesta. Algoritmus silně spoléhá na cik-cak součin.

Zhruba řečeno, pro vyřešení problému neorientované konektivity st v logaritmickém paměťovém prostoru je původní graf transformován pomocí kombinace součinu a klikatého součinu na pravidelný graf konstantního stupně s logaritmickým průměrem. Produkt zvětšuje rozteč (zvětšením průměru) zvýšením stupně a cik-cak produkt se používá ke snížení stupně při zachování rozprostření.

Viz také

Operace s grafy

Poznámky

↑ Reingold, Vadhan, Wigderson, 2000 , str. 3-13.
↑ Omer Reingold. Nepřímá konektivita v log-space // Journal of the ACM . - 2008. - T. 55 , no. 4 . - S. 24 . - doi : 10.1145/1391289.1391291 .
↑ Reingold, Vadhan, Wigderson, 2000 .

Literatura

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