Cikkcakkszorzat

A matematika, azon belül a gráfelmélet területén a G és H gráfok cikkcakkszorzata (zig-zag product) egy gráfszorzás, olyan kétváltozós gráfművelet, amely reguláris gráfok rendezett párjaihoz egy új gráfot rendel. A ${\displaystyle G\circ H}$, eredetileg ${\displaystyle G}$ Ⓩ ${\displaystyle H}$ cikkcakkszorzat vesz egy nagyméretű (${\displaystyle G}$) és egy kisméretű (${\displaystyle H}$) reguláris gráfot, és eredményül olyan gráfot ad, ami lehetőség szerint mindkét gráf számunkra kívánatos tulajdonságait örökli: az egyik gráfban bármely két csúcs között létezik rövid út, a másik pedig állandó fokszámú. A szorzatgráf konstans fokszámú lesz, és mégis rövid úton el lehet jutni tetszőleges csúcsából egy másikba. A cikkcakkszorzat fontos tulajdonsága, hogy ha ${\displaystyle H}$ jó expander, akkor az eredménygráf expanziója alig rosszabb ${\displaystyle G}$ expanziójánál.

Nagy vonalakban a ${\displaystyle G\circ H}$ cikkcakk-gráfszorzat ${\displaystyle G}$ minden csúcsát lecseréli a ${\displaystyle H}$ egy kópiájával (felhőjével), a csúcsokat pedig úgy köti össze, hogy először egy kis lépést (cikk) tesz a felhőben, majd egy nagy lépést (cakk), majd még egy kis lépést a célfelhőben.

A cikkcakkszorzatot (Reingold, Vadhan & Wigderson 2000) vezette be. Megjelenésekor a konstans fokú expanderek és extraktorok explicit konstrukciójához használták. Később a cikkcakkszorzatot a számítási bonyolultságelméletben az SL és L bonyolultsági osztályok azonosságának bizonyítására használták fel (Reingold 2008), amiért később megkapták a Gödel-díjat.^[1]

1. ↑ Gödel-díj 2009 Archiválva 2016. március 3-i dátummal a Wayback Machine-ben.