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 $G\circ H$, eredetileg $G$ Ⓩ $H$ cikkcakkszorzat vesz egy nagyméretű ($G$) és egy kisméretű ($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 $H$ jó expander, akkor az eredménygráf expanziója alig rosszabb $G$ expanziójánál. Nagy vonalakban a $G\circ H$ cikkcakk-gráfszorzat $G$ minden csúcsát lecseréli a $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.

Definíciók

Az alábbiakban szereplő gráfok mind irányítatlanok és regulárisak, továbbá az első gráf fokszáma megfelel a második gráf csúcsai számának.

Egyszerűsített definíció

A szerzők munkáját követve tekintsük először a cikkcakkszorzat egyszerűsített változatát. Ebben a definícióban csak olyan $D$-reguláris gráfokat tekintsünk, melyek $D$ színnel élszínezhetők. Egy ilyen „jó” élszínezésben az ugyanabból a csúcsból kiinduló bármely két él különböző színű. Legyen $G$ $D$-reguláris gráf $N$ csúccsal, továbbá $H$ egy $d$-reguláris gráf $D$ csúccsal. Vegyük észre, hogy $D$ megegyezik $G$ fokszámával, $G$ színeinek számával és $H$ csúcsainak számával is: $H$ csúcsait tetszőlegesen kiszínezzük ezzel a $D$ színnel.

• 
  A 4-reguláris G a bal oldalon, az 1-reguláris H a jobbon.
• 
  G csúcsait kicseréltük H-ból álló felhőkre.
• 
  A cikkcakk-élek cseréjének művelete.
• 
  Az eredményül kapott $G\circ H$ 1-reguláris.

A következő lépésekkel nyerhető ki $G$ és $H$ cikkcakkszorzata, melyet $G\circ H$-val jelölünk:

• Cseréljük ki $G$ minden csúcsát a $H$ gráf egy-egy kópiájára, avagy „felhőjére”.
• Az eredménygráf két csúcsa, $v$ és $w$ akkor szomszédosak, hogyha létezik olyan $a$ és $b$ csúcs, melyekre:
  • $v$ és $a$ szomszédosak $H$-ban (a „cikk”-ben);
  • $a$ és $b$ azonos színűek, és $G$-ben szomszédos csúcsokból származtatott felhőkhöz tartoznak ;
  • $b$ és $w$ szomszédosak $H$-ban (a „cakk”-ban);.

Az eredménygráf:

• $N\cdot D$ csúcsot tartalmaz, hiszen a $G$ $N$ csúcsát egyenként kicseréltük a $D$ csúcsot tartalmazó $H$-kkkal;
• fokszáma $d^2$, hiszen adott csúcsból $d$ lehetőség van a „cikk”-re, egyetlen lehetőség a köztes lépésre majd újabb $d$ lépés a „cakk”-ra.

• 
  Ezúttal H 2-reguláris.
• 
  A csúcsok cseréje után.
• 
  A cikkcakk.
• 
  Az eredményül kapott $G\circ H$ most 4-reguláris.

A rotáció alkalmazása

Az általános esetben nem tehető fel, hogy ismert a gráf D-élszínezése. Számozzuk meg az egy-egy csúcsból kiinduló éleket egész számokkal, az $N$ csúcsú gráf esetében $1$ - $N$-ig, jelöljük ezt $[N]$-nel. A $(v,i)$ rendezett pár jelölje a $v$ csúcsból kiinduló $i$-edik élt. Feltételezve, hogy $G$ $D$-reguláris (minden csúcs fokszáma $D$), a

${\mathrm{R}\mathrm{o}\mathrm{t}}_G:[N]\times [D]\to [N]\times [D]$

rotáció alkalmazása a következőképp történik:

${\mathrm{R}\mathrm{o}\mathrm{t}}_G(v,i)=(w,j),$

amennyiben a $v$-ből kijövő $i$-edik él $w$-be vezet és a $w$-ből kijövő $j$-edik él $v$-be; tehát ha a $[v,w]$ él létezik, akkor az a $v$-ből kijövő $i$-edik él, valamint a $w$-ből kijövő $j$-edik él. A rotáció alkalmazása helyettesíti, illetve általánosítja az előző definíció élszínezési feltételét. Ha egy D színnel történő színezés lehetséges, akkor lehetséges a csúcsok körüli éleket úgy számozni, hogy $i=j$ fennálljon. A definícióból következik, hogy ${\mathrm{R}\mathrm{o}\mathrm{t}}_G$ bijekció, továbbá ${\mathrm{R}\mathrm{o}\mathrm{t}}_G\circ {\mathrm{R}\mathrm{o}\mathrm{t}}_G$ megegyezik az identitásfüggvénnyel; más szavakkal, a ${\mathrm{R}\mathrm{o}\mathrm{t}}_G$ egy involúció.

Definíció

A cikkcakkszorzat működési elve az általános esetben.

Legyen $G$ egy $D$-reguláris gráf az $[N]$ csúcshalmazon a ${\mathrm{R}\mathrm{o}\mathrm{t}}_G$ rotációs leképezéssel és legyen $H$ egy $d$-reguláris gráf a $[D]$ csúcshalmazon a ${\mathrm{R}\mathrm{o}\mathrm{t}}_H$ rotációs leképezéssel. A $G\circ H$ cikkcakkszorzat ekkor egy $d^2$-reguláris gráf az $[N]\times [D]$ csúcshalmazon, melynek rotációs térképe ${\mathrm{R}\mathrm{o}\mathrm{t}}_{G\circ H}$, méghozzá:
${\mathrm{R}\mathrm{o}\mathrm{t}}_{G\circ H}((v,a),(i,j))$:

1. Legyen $(a^{\prime },i^{\prime })={\mathrm{R}\mathrm{o}\mathrm{t}}_H(a,i)$.
2. Legyen $(w,b^{\prime })={\mathrm{R}\mathrm{o}\mathrm{t}}_G(v,a^{\prime })$.
3. Legyen $(b,j^{\prime })={\mathrm{R}\mathrm{o}\mathrm{t}}_H(b^{\prime },j)$.
4. Kimenet $((w,b),(j^{\prime },i^{\prime }))$.

A $G\circ H$ gráf csúcsai $[N]\times [D]$-beli $(v,a)$ párosok. A gráf élei a $d$-reguláris gráf $(i,j)$ címkéit viszik tovább, melyek az adott csúcsból kiinduló két döntésnek felelnek meg.

Tulajdonságok

Fokszámredukció

A definícióból következően a cikkcakkszorzat a $G$ gráfból egy új, $d^2$-reguláris gráfot állít elő. Tehát ha $G$ jelentősen nagyobb $H$-nál, a cikkcakkszorzat csökkenteni fogja $G$ fokszámát. Nagy vonalakban az történik, hogy a $G$ egyes csúcsait $H$ méretű felhővé amplifikálva (felerősítve), az eredeti csúcshoz tartozó élek elosztásra kerülnek a csúcsot helyettesítő felhő csúcsai között.

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

Egy gráf expanziója a gráf spektrális résével mérhető. A cikkcakkszorzat fontos tulajdonsága a spektrális rés megőrzése. Tehát, ha $H$ egy „elég jó” expander (nagy a spektrális rése), akkor a cikkcakkszorzat expanziója közel van $G$ eredeti expanziójához. Formálisan: Legyen az $(N,D,\lambda )$-gráf egy $N$ csúcsú $D$-reguláris gráf, melynek (a kapcsolódó véletlen sétájának) második legnagyobb sajátértéke abszolút értékben legfeljebb $\lambda$. Legyen $G_1$ egy $(N_1,D_1,{\lambda }_1)$-gráf és $G_2$ egy $(D_1,D_2,{\lambda }_2)$-gráf; ekkor $G\circ H$ egy $(N_1\cdot D_1,D_2^2,f({\lambda }_1,{\lambda }_2))$-gráf, ahol $f({\lambda }_1,{\lambda }_2)<{\lambda }_1+{\lambda }_2+{\lambda }_2^2$.

Az összefüggőség megőrzése

A $G\circ H$ cikkcakkszorzat $G$ minden összefüggő komponensére külön hat. Formálisan, ha adott két gráf: $G$, egy $D$-reguláris gráf $[N]$ csúcshalmazon és $H$, egy $d$-reguláris gráf a $[D]$ csúcshalmazon – akkor ha $S\subseteq [N]$ $G$ összefüggő komponense, akkor $G{|}_S\circ H=G\circ H{|}_{S\times D}$, ahol $G{|}_S$ a $G$ $S$ által feszített részgráfja (tehát a gráf $S$ csúcsaival, ami tartalmazza a $G$ összes olyan élét, ami $S$ csúcsai között húzódik).

Alkalmazások

Konstans fokszámú expanderek konstrukciója

2002-ben Omer Reingold, Salil Vadhan és Avi Wigderson megadtak egy egyszerű, explicit kombinatorikus konstrukciót a konstans fokszámú expander gráfok előállítására. A konstrukció iteratív, egyetlen, egyszerű építőeleme egy konstans méretű expandert használ. A cikkcakkszorzat minden iteráció során előállít egy új, megnövelt méretű, de változatlan fokszámú és expanziójú gráfot. Ezzel a módszerrel tetszőlegesen nagy expanderek létrehozhatók. A cikkcakkszorzat fent említett tulajdonságaiból látható, hogy egy nagy gráf kis gráffal való szorzata a nagy gráf méretéhez és a kis gráf fokszámához hasonló lesz, megőrizve mindkettő expanziós tulajdonságait, így lehetővé téve az expander méretének káros mellékhatások nélküli növelését.

Az irányítatlan st-elérhetőségi probléma logaritmikus térben történő megoldása

2005-ben Omer Reingold bemutatott egy algoritmust, ami logaritmikus térben megoldja az irányítatlan st-elérhetőségi problémát, azaz annak a problémáját, hogy egy irányítatlan gráf két csúcsa között létezik-e út. Az algoritmus erősen épít a cikkcakkszorzás műveletére. A probléma megoldásához a bemeneti gráf hatványozás és cikkcakkszorzat kombinációjával transzformálásra kerül egy konstans fokszámú, logaritmikus átmérőjű reguláris gráffá. A hatványozás a fokszám növelésének árán növeli az expanziót (így csökkenti az átmérőt), a cikkcakkszorzat pedig csökkenti a fokszámot és megtartja az expanziót.

Fordítás

• Ez a szócikk részben vagy egészben a Zig-zag product című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
• Ez a szócikk részben vagy egészben a Produit zig-zag de graphes című francia Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• Véletlen séta gráfokon, expanderek (Szabó Dániel BSC szakdolgozat)

Források

• Reingold, O.; Vadhan, S. & Wigderson, A. (2000), "Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors", Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 3–13, DOI 10.1109/SFCS.2000.892006.
• Reingold, O (2008), "Undirected connectivity in log-space", Journal of the ACM 55 (4): Article 17, 24 pages, DOI 10.1145/1391289.1391291.
• Reingold, O.; Trevisan, L. & Vadhan, S. (2006), "Pseudorandom walks on regular digraphs and the RL vs. L problem", Proc. 38th ACM Symposium on Theory of Computing (STOC), pp. 457–466, DOI 10.1145/1132516.1132583.