Sicksack produkt

I grafteorin tar sicksackprodukten av vanliga grafer (betecknad ) en stor graf och en liten graf och skapar en graf som är ungefär lika stor som den stora grafen men kraften hos den lilla. En viktig egenskap hos sicksackprodukten är att för en bra expander är spridningen av den resulterande grafen bara något sämre än spridningen av grafen . $G,H$ $G\circ H$ $G$ $H$ $H$ $G$

Grovt sett ersätter sicksackprodukten varje hörn av grafen med en kopia (moln) av grafen och förbinder hörnen genom att ta ett litet steg (sick) inuti molnet, och sedan ett stort steg (sack) mellan de två molnen, och ytterligare ett litet steg in i det sista molnet. $G\circ H$ $G$ $H$

Sicksackprodukten introducerades av Reingold, Wadhan och Wigderson [1] . Sicksackprodukten användes ursprungligen för att uttryckligen konstruera expanderare och extraktorer med konstant grad. Senare användes sicksackprodukten i beräkningskomplexitetsteori för att bevisa likheten mellan SL och L [2] .

Definition

Låt vara en -regelbunden graf över c rotation , och låt vara -regelbunden graf över c rotationsmappning . $G$ $D$ $[N]$ $\mathrm {Rot} _{G}$ $H$ $d$ $[D]$ $\mathrm {Rot} _{H}$

En sicksackprodukt definieras som en -regelbunden graf över , vars rotation definieras enligt följande : $G\circ H$ ${\displaystyle d^{2))$ $[N]\ gånger [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'))$ .

Egenskaper

Minskande grad

Det följer direkt av definitionen av sicksackprodukten att grafen förvandlas till en ny -regelbunden graf. Således, om väsentligt större än , minskar sicksackprodukten graden av . $G$ ${\displaystyle d^{2))$ $G$ $H$ $G$

Grovt sett förvandlar sicksackprodukten varje hörn av grafen till ett moln av samma storlek som grafen och fördelar bågarna för varje ursprunglig vertex till hörnen på molnet som ersatte det. $G$ $H$

Bevarande av spektralgapet

Spridningen av en graf kan mätas genom dess spektralgap. En viktig egenskap hos sicksackprodukten är bevarandet av spektralgapet . Således, om expandern är "tillräckligt bra" (har ett stort spektralgap), så är spridningen av sicksackprodukten nära den ursprungliga spridningen av grafen . $H$ $G$

Formellt: definieras som valfri -reguljär vertexgraf vars näst största egenvärde har ett absolutvärde på minst . $(N,D,\lambda )$ $D$ $N$ $\lambda$

Låt — och — vara två grafer, då är en graf , där . ${\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})$

Bevarande av anknytning

Sicksack-produkten fungerar separat för varje ansluten komponent i grafen . $G\circ H$ $G$

Formellt: låt två grafer ges: — -regelbunden graf över och — -regelbunden graf över . Om är en ansluten komponent i grafen , då , där är en subgraf av grafen som bildas av hörn (det vill säga en graf över , som innehåller alla bågar från mellan hörn från ). $G$ $D$ $[N]$ $H$ $d$ $[D]$ $S\subseteq [N]$ $G$ ${\displaystyle G|_{S}\cirkel H=G\cirkel H|_{S\ gånger D))$ $G|_{S}$ $G$ $S$ $S$ $G$ $S$

Applikationer

Konstruktion av expanderare med konstant grad

År 2002 visade Omer Reingold, Salil Wadhan och Avi Widgerson [3] en enkel explicit kombinatorisk konstruktion av konstantgradsexpanderare. Konstruktionen görs iterativt och kräver en expanderare av konstant grad som grund. Vid varje iteration används sicksackprodukten för att skapa ytterligare en graf vars storlek ökar, men graden och fördelningen förblir densamma. Genom att upprepa processen kan godtyckligt stora expanderare skapas.

Lösning av det oriktade anslutningsproblemet i ett logaritmiskt minnesutrymme

2005 introducerade Ömer Reingold en algoritm för att lösa st-anslutningsproblemet med hjälp av ett logaritmiskt minnesutrymme. Problemet är att kontrollera om det finns en väg mellan två givna hörn av en oriktad graf. Algoritmen förlitar sig mycket på sicksackprodukten.

Grovt sett, för att lösa det oriktade anslutningsproblemet st i ett logaritmiskt minnesutrymme, transformeras den ursprungliga grafen med en kombination av en produkt och en sicksackprodukt till en vanlig graf med konstant grad med en logaritmisk diameter. Produkten ökar spridningen (genom att öka diametern) genom att öka graden, och sicksackprodukten används för att minska graden med bibehållen spridning.

Se även

Operationer på grafer

Anteckningar

↑ Reingold, Vadhan, Wigderson, 2000 , sid. 3-13.
↑ Omer Reingold. Oriktad anslutning i loggutrymme // Journal of the ACM . - 2008. - T. 55 , nr. 4 . - S. 24 . - doi : 10.1145/1391289.1391291 .
↑ Reingold, Vadhan, Wigderson, 2000 .

Litteratur

Omer Reingold, Salil Vadhan, Avi Wigderson. Proc. 41:a 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:e ACM Symposium on Theory of Computing (STOC) . - 2006. - S. 457-466 . - doi : 10.1145/1132516.1132583 .