Siksak tuote

Graafiteoriassa säännöllisten graafien siksaktulo ( merkitty ) ottaa suuren ja pienen graafin ja luo graafin, joka on suunnilleen suuren graafin kokoinen, mutta pienen tehon suuruinen. Tärkeä siksak-tuotteen ominaisuus on, että hyvällä laajentimella saadun graafin leviäminen on vain hieman huonompi kuin graafin leviäminen . $G,H$ $G\circ H$ $G$ $H$ $H$ $G$

Karkeasti sanottuna siksak-tulo korvaa graafin jokaisen kärjen graafin kopiolla (pilvi) ja yhdistää kärjet ottamalla pienen askeleen (sik) pilven sisällä ja sitten suuren askeleen (sak) kahden pilven välillä, ja toinen pieni askel viimeisen pilven sisällä. $G\circ H$ $G$ $H$

Siksak-tuotteen esittelivät Reingold, Wadhan ja Wigderson [1] . Siksak-tuotetta käytettiin alun perin nimenomaan vakioasteisten laajenninten ja irrottimien rakentamiseen. Myöhemmin siksak-tuloa käytettiin laskennallisessa monimutkaisuusteoriassa todistamaan SL ja L [2] yhtäläisyys .

Määritelmä

Olkoon -säännöllinen kuvaaja c-kierron yli ja olkoon -säännöllinen kuvaaja c - rotaatiomappauksen yli . $G$ $D$ ${\näyttötyyli [N]}$ $\mathrm {Rot} _{G}$ $H$ $d$ ${\näyttötyyli [D]}$ $\mathrm {Rot} _{H}$

Siksak -tulo määritellään säännölliseksi graafiksi yli , jonka kierto on määritelty seuraavasti : $G\circ H$ ${\displaystyle d^{2))$ ${\näyttötyyli [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'))$ .

Ominaisuudet

Vähenevä aste

Siksak-tulon määritelmästä seuraa suoraan, että graafi muunnetaan uudeksi -säännölliseksi graafiksi. Siten, jos olennaisesti suurempi kuin , siksak-tuote pienentää :n astetta . $G$ ${\displaystyle d^{2))$ $G$ $H$ $G$

Karkeasti sanottuna siksak-tulo muuttaa graafin jokaisen kärjen graafin kokoiseksi pilveksi ja jakaa jokaisen alkuperäisen kärjen kaaret sen korvanneen pilven kärkeen. $G$ $H$

Spektriaukon säilyminen

Graafin leviämistä voidaan mitata sen spektrivälillä. Tärkeä siksak-tuotteen ominaisuus on spektrivälin säilyminen . Siten, jos laajentaja on "riittävän hyvä" (sillä on suuri spektrirako), niin siksak-tuotteen leviäminen on lähellä graafin alkuperäistä leviämistä . $H$ $G$

Muodollisesti: määritellään mikä tahansa -säännöllinen huippupistegraafi, jonka toiseksi suurimman ominaisarvon absoluuttinen arvo on vähintään . ${\näyttötyyli (N,D,\lambda )}$ $D$ $N$ $\lambda$

Olkoon — ja — kaksi kuvaajaa, niin on graafi , jossa . $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})$

Yhteyden säilyttäminen

Siksak-tuote toimii erikseen jokaiselle kaavion yhdistetylle komponentille . $G\circ H$ $G$

Muodollisesti: olkoon kaksi kuvaajaa: — -säännöllinen graafi yli ja — -säännöllinen graafi yli . Jos on graafin yhdistetty komponentti , Sitten , Jossa on pisteiden muodostama graafin osagraafi (eli graafin yli , joka sisältää kaikki kaaret alkaen pisteiden välistä ). $G$ $D$ ${\näyttötyyli [N]}$ $H$ $d$ ${\näyttötyyli [D]}$ $S\subseteq [N]$ $G$ ${\displaystyle G|_{S}\circ H=G\circ H|_{S\times D))$ $G|_{S}$ $G$ $S$ $S$ $G$ $S$

Sovellukset

Vakioasteen laajenninten rakentaminen

Vuonna 2002 Omer Reingold, Salil Wadhan ja Avi Widgerson [3] osoittivat yksinkertaisen eksplisiittisen kombinatorisen rakenteen vakioasteen laajennuksista. Rakentaminen tehdään iteratiivisesti ja vaatii pohjana vakioasteisen laajentimen. Jokaisessa iteraatiossa siksak-tuloa käytetään luomaan toinen graafi, jonka koko kasvaa, mutta aste ja jakauma pysyvät samoina. Toistamalla prosessia voidaan luoda mielivaltaisen suuria laajennuksia.

Ohjaamattoman st-yhteysongelman ratkaiseminen logaritmisessa muistitilassa

Ömer Reingold esitteli vuonna 2005 algoritmin st-yhteysongelman ratkaisemiseksi käyttämällä logaritmista muistitilaa. Ongelmana on tarkistaa, onko suuntaamattoman graafin kahden tietyn kärjen välillä polku. Algoritmi on vahvasti riippuvainen siksak-tuotteesta.

Karkeasti sanottuna logaritmisen muistiavaruuden suuntaamattoman liitettävyysongelman st ratkaisemiseksi alkuperäinen graafi muunnetaan käyttämällä tulon ja siksaktulon yhdistelmää säännölliseksi graafiksi, jolla on vakioasteinen logaritminen halkaisija. Tuote lisää leviämistä (halkaisijaa lisäämällä) lisäämällä astetta, ja siksak-tuotetta käytetään asteen pienentämiseen samalla kun leviäminen säilyy.

Katso myös

Toiminnot kaavioilla

Muistiinpanot

↑ Reingold, Vadhan, Wigderson, 2000 , s. 3-13.
↑ Omer Reingold. Ohjaamaton yhteys lokiavaruudessa // Journal of the ACM . - 2008. - T. 55 , no. 4 . - S. 24 . - doi : 10.1145/1391289.1391291 .
↑ Reingold, Vadhan, Wigderson, 2000 .

Kirjallisuus

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 Symposium on Theory of Computing (STOC) . - 2006. - S. 457-466 . - doi : 10.1145/1132516.1132583 .