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 , eredetileg Ⓩ cikkcakkszorzat vesz egy nagyméretű () és egy kisméretű () 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 jó expander, akkor az eredménygráf expanziója alig rosszabb expanziójánál.
Nagy vonalakban a cikkcakk-gráfszorzat minden csúcsát lecseréli a 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 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 , amiért később megkapták a Gödel-díjat.Gödel-díj 2009 .
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 -reguláris gráfokat tekintsünk, melyek színnel Ez kizárja például a páratlan csúcsból álló körgráfokat, melyek 2-regulárisak de csak 3 színnel (él)színezhetők. é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 -reguláris gráf csúccsal, továbbá egy -reguláris gráf csúccsal. Vegyük észre, hogy megegyezik fokszámával, színeinek számával és csúcsainak számával is: csúcsait tetszőlegesen kiszínezzük ezzel a színnel.
A következő lépésekkel nyerhető ki és cikkcakkszorzata, melyet A szerzők bonyolultabb jelölést használtak – Ⓩ –, melyet nem sikerült a Wikipédia Latexében reprodukálni.-val jelölünk: Cseréljük ki minden csúcsát a gráf egy-egy kópiájára, avagy „felhőjére”. Az eredménygráf két csúcsa, és akkor szomszédosak, hogyha létezik olyan és csúcs, melyekre: és szomszédosak -ban (a „cikk”-ben); és azonos színűek, és -ben szomszédos csúcsokból származtatott felhőkhöz tartoznak ; és szomszédosak -ban (a „cakk”-ban);.
Az eredménygráf: csúcsot tartalmaz, hiszen a csúcsát egyenként kicseréltük a csúcsot tartalmazó -kkkal; fokszáma , hiszen adott csúcsból lehetőség van a „cikk”-re, egyetlen lehetőség a köztes lépésre majd újabb lépés a „cakk”-ra.
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 csúcsú gráf esetében - -ig, jelöljük ezt -nel. A rendezett pár jelölje a csúcsból kiinduló -edik élt.
Feltételezve, hogy -reguláris (minden csúcs fokszáma ), a
rotáció alkalmazása a következőképp történik:
amennyiben a -ből kijövő -edik él -be vezet és a -ből kijövő -edik él -be; tehát ha a él létezik, akkor az a -ből kijövő -edik él, valamint a -ből kijövő -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 fennálljon.
A definícióból következik, hogy bijekció, továbbá megegyezik az identitásfüggvénnyel; más szavakkal, a egy involúció.
Definíció
Legyen egy -reguláris gráf az csúcshalmazon a rotációs leképezéssel és legyen egy -reguláris gráf a csúcshalmazon a rotációs leképezéssel. A cikkcakkszorzat ekkor egy -reguláris gráf az csúcshalmazon, melynek rotációs térképe , méghozzá: : Legyen . Legyen . Legyen . Kimenet .
A gráf csúcsai -beli párosok. A gráf élei a -reguláris gráf 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 gráfból egy új, -reguláris gráfot állít elő. Tehát ha jelentősen nagyobb -nál, a cikkcakkszorzat csökkenteni fogja fokszámát. Nagy vonalakban az történik, hogy a egyes csúcsait 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 egy „elég jó” expander (nagy a spektrális rése), akkor a cikkcakkszorzat expanziója közel van eredeti expanziójához.
Formálisan: Legyen az -gráf egy csúcsú -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 .
Legyen egy -gráf és egy -gráf; ekkor egy -gráf, ahol .
Az összefüggőség megőrzése A cikkcakkszorzat minden összefüggő komponensére külön hat.
Formálisan, ha adott két gráf: , egy -reguláris gráf csúcshalmazon és , egy -reguláris gráf a csúcshalmazon – akkor ha összefüggő komponense, akkor , ahol a által feszített részgráfja (tehát a gráf csúcsaival, ami tartalmazza a összes olyan élét, ami 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
További információk Véletlen séta gráfokon, expanderek (Szabó Dániel BSC szakdolgozat)
Jegyzetek
Források . . .
Kategória:Gráfszorzatok