Cikcakkos termék

A gráfelméletben a szabályos gráfok cikk- cakk szorzata (jelölése ) vesz egy nagy gráfot és egy kis gráfot , és egy nagyjából akkora gráfot hoz létre, mint a nagy gráf, de a kicsi teljesítménye. A cikk-cakk szorzat fontos tulajdonsága, hogy egy jó expander esetén a kapott gráf terjedése csak kicsivel rosszabb, mint a gráf terjedése . $G,H$ $G\circ H$ $G$ $H$ $H$ $G$

Nagyjából elmondható, hogy a cikk-cakk szorzat a gráf minden csúcsát a gráf másolatával (felhővel) helyettesíti, és a csúcsokat egy kis lépéssel (zig) köti össze a felhő belsejében, majd egy nagy lépést (zag) a két felhő között, és még egy kis lépés a végső felhő belsejében. $G\circ H$ $G$ $H$

A cikkcakk terméket Reingold, Wadhan és Wigderson vezette be [1] . A cikk-cakk terméket eredetileg kifejezetten állandó fokú expanderek és extraktorok készítésére használták. Később a cikk-cakk szorzatot a számítási komplexitáselméletben használták az SL és L egyenlőségének bizonyítására [2] .

Definíció

Legyen egy szabályos gráf c - forgatás felett , és legyen -reguláris gráf c-forgatás felett . $G$ $D$ $[N]$ $\mathrm {Rot} _{G}$ $H$ $d$ ${\megjelenítési stílus [D]}$ $\mathrm {Rot} _{H}$

A cikk-cakk szorzat egy szabályos gráf felett van definiálva , amelynek elforgatását a következőképpen határozzuk meg : $G\circ H$ $d^{2}$ ${\megjelenítési stílus [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'))$ .

Tulajdonságok

Csökkenő fok

A cikk-cakk szorzat definíciójából egyenesen következik, hogy a gráf egy új -reguláris gráfrá alakul. Így, ha lényegesen nagyobb, mint , a cikk-cakk szorzat csökkenti a mértékét . $G$ $d^{2}$ $G$ $H$ $G$

Nagyjából elmondható, hogy a cikk-cakk szorzat a gráf minden csúcsát a gráf méretű felhővé alakítja, és minden eredeti csúcs íveit elosztja a helyébe lépő felhő csúcsai között. $G$ $H$

A spektrális rés megőrzése

Egy gráf terjedése a spektrális résével mérhető. A cikk-cakk termék fontos tulajdonsága a spektrális rés megmaradása . Így, ha az expander "elég jó" (nagy spektrális rése van), akkor a cikk-cakk szorzat szórása közel van a gráf eredeti terjedéséhez . $H$ $G$

Formálisan: bármely olyan reguláris csúcsgráfként definiálható, amelynek második legnagyobb sajátértéke abszolút értéke legalább . $(N,D,\lambda )$ $D$ $N$ $\lambda$

Legyen — és — két gráf, akkor van egy gráf , ahol . $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})$

Összeköttetés megőrzése

A cikk-cakk szorzat a grafikon minden egyes összekapcsolt összetevőjére külön működik . $G\circ H$ $G$

Formálisan: legyen két gráf megadva: — -regular graph over és — -regular graph over . Ha a gráf összefüggő komponense , akkor , ahol a gráf csúcsokból alkotott részgráfja (vagyis egy feletti gráf , amely tartalmazza az összes ívet a csúcsok közötti csúcsokból ). $G$ $D$ $[N]$ $H$ $d$ ${\megjelenítési stílus [D]}$ $S\subseteq [N]$ $G$ ${\displaystyle G|_{S}\circ H=G\circ H|_{S\times D))$ $G|_{S}$ $G$ $S$ $S$ $G$ $S$

Alkalmazások

Állandó fokozatú bővítők építése

2002 -ben Omer Reingold, Salil Wadhan és Avi Widgerson [3] egy egyszerű, explicit kombinatorikus konstrukciót mutatott be állandó fokozatú bővítőkről. A konstrukció iteratív módon történik, és alapként állandó fokú bővítőt igényel. Minden iterációnál a cikk-cakk szorzatot egy másik gráf létrehozására használjuk, amelynek mérete növekszik, de a foka és az eloszlás változatlan marad. A folyamat megismétlésével tetszőleges nagy bővítők hozhatók létre.

Az irányítatlan st kapcsolódási probléma megoldása logaritmikus memóriatérben

2005-ben Ömer Reingold bevezetett egy algoritmust az st-kapcsolati probléma megoldására logaritmikus memóriaterület felhasználásával. A probléma annak ellenőrzése, hogy van-e út egy irányítatlan gráf két megadott csúcsa között. Az algoritmus nagymértékben támaszkodik a cikk-cakk termékre.

Durván fogalmazva, az st irányítatlan kapcsolódási probléma logaritmikus memóriatérben történő megoldásához az eredeti gráfot egy szorzat és egy cikk-cakk szorzat kombinációjával egy állandó fokszámú, logaritmikus átmérőjű szabályos gráfrá alakítjuk. A termék a szórást növeli (az átmérő növelésével) a fok növelésével, a cikkcakk termék pedig a fok csökkentésére szolgál, miközben a szórást megtartja.

Lásd még

Műveletek grafikonokon

Jegyzetek

↑ Reingold, Vadhan, Wigderson, 2000 , p. 3-13.
↑ Omer Reingold. Irányítatlan kapcsolat a naplótérben // Az ACM naplója . - 2008. - T. 55 , sz. 4 . - S. 24 . - doi : 10.1145/1391289.1391291 .
↑ Reingold, Vadhan, Wigderson, 2000 .

Irodalom

Omer Reingold, Salil Vadhan, Avi Wigderson. Proc. 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. Proc. 38. ACM szimpózium a számítástechnikai elméletről (STOC) . - 2006. - S. 457-466 . - doi : 10.1145/1132516.1132583 .