Produkt zygzakowaty

W teorii grafów iloczyn zygzakowaty grafów regularnych $\$ oznaczony przez , jest operacją binarną $,$ która pobiera duży wykres ( $Displaystyle G \ circ$ $displaystyle G}$ ) i mały wykres ( $) i tworzy wykres, który w przybliżeniu$ rozmiar dużego, ale stopień małego. Ważną właściwością iloczynu zygzakowatego jest to, że jeśli $jest$ dobrym ekspanderem , to rozwinięcie wynikowego wykresu jest tylko nieznacznie gorsze $.$

$Z grubsza$ $zastępuje$ zygzakowaty każdy wierzchołek $i$ (chmury) łączy wierzchołki, mały krok (zig) wewnątrz chmury, po którym następuje duży krok (zag) między dwiema chmurami, a na końcu wykonuje kolejny mały krok wewnątrz chmury docelowej.

Iloczyn zygzakowaty został wprowadzony przez Reingolda, Vadhana i Wigdersona (2000) . Kiedy po raz pierwszy wprowadzono produkt zygzakowaty, był on używany do jawnej konstrukcji ekspanderów i ekstraktorów o stałym stopniu. Później iloczyn zygzakowaty był używany w teorii złożoności obliczeniowej , aby udowodnić, że symetryczna przestrzeń logarytmiczna i logarytm są równe ( Reingold 2008 ).

Definicja

Niech $będzie$ $\ Displaystyle$ wykresem na $N]}$ z mapą rotacji ${\ Displaystyle \ operatorname {Rot} _ {G}$ } niech będzie $\ displaystyle$ wykresem na $}$ $[ D$ z mapą obrotu ${\ Displaystyle \ operatorname {Rot} _ {H}}$ . Produkt zygzakowaty jest zdefiniowany jako regularny wykres na $]}$ $\$ $d ^ {2}$ $}$ $sol$ mapa następująca
${\ Displaystyle \ operatorname {Rot} _ {G \ circ H} ((v, a), (i, j))}$ :

Niech ${\ Displaystyle (a', i') = \ operatorname {Rot} _ {H} (a, i)}$ .
Niech ${\ Displaystyle (w, b ') = \ operatorname {Rot} _ {G} (v, a')}$ .
Niech ${\ Displaystyle (b, j ') = \ operatorname {Rot} _ {H} (b', j)}$ .
Wyjście ${\ Displaystyle ((w, b), (j', i'))}$ .

Nieruchomości

Obniżenie stopnia

Bezpośrednio z definicji iloczynu zygzakowatego wynika, że przekształca on wykres $,$ $wykres$ który jest regularny Zatem jeśli $, iloczyn$ jest znacznie większy niż $displaystyle$ zmniejszy stopień $G}$ . Z $\ displaystyle H$ mówiąc, wzmacniając każdy wierzchołek w chmurę wielkości $}$ produkt w rzeczywistości dzieli krawędzie każdego oryginalnego wierzchołka między wierzchołki chmury, które go zastępują.

Zachowanie luki widmowej

Ekspansja wykresu może być mierzona jego luką widmową , przy czym ważną właściwością iloczynu zygzakowatego jest zachowanie luki widmowej. Oznacza to, że jeśli $,$ to ekspansja iloczynu zygzakowatego jest zbliżona do pierwotnej ekspansji $\ displaystyle G}$ .

$N, D, \ lambda$ : Zdefiniuj $( N , re$ jako dowolny -regularny wykres na wierzchołkach, których druga co do wielkości wartość własna $($ powiązanego błądzenia losowego) ma co najwyżej wartość bezwzględną ${\ displaystyle \ lambda}$ .

Niech ${\ Displaystyle G_ {1}}$ będzie za ${\ Displaystyle (N_ {1}, D_ {1}, \ lambda _ {1})}$ -graf i ${\ Displaystyle G_ {2}}$ być za ${\ Displaystyle (D_ {1}, D_ {2}, \ lambda _ {2})}$ -graf, a następnie ${\ Displaystyle G_ {1} \ cyrk G_ {2}}$ jest za ${\ Displaystyle (N_ {1} \ cdot D_ {1}, D_ {2} ^ {2}, f (\ lambda _{1},\lambda _{2})}}$ -wykres, gdzie ${\ Displaystyle f (\ lambda _ {1}, \ lambda _ {2}) <\ lambda _ {1} + \ lambda _ {2} + \ lambda _ {2} ^ {2}}$ .

Zachowanie łączności

Produkt zygzakowaty działa oddzielnie na każdym połączonym komponencie $\ circ H}$ ${\ Displaystyle$ .

Formalnie rzecz biorąc, biorąc pod uwagę dwa wykresy: sol ${\ displaystyle G}$ za ${\ displaystyle D}$ - regularny wykres na ${\ Displaystyle [N]}$ i ${\ Displaystyle H}$ , za ${\ displaystyle d}$ -wykres regularny na $]}$ - jeśli jest połączonym składnikiem ${\ displaystyle S \ subseteq [N$ $}$ wtedy ${\ Displaystyle G | _ {S} \ circ H = G \ circ H | _ {S \ razy D}}$ , gdzie $| _ {S}}$ $Displaystyle$ jest podwykresem indukowanym przez (tj $} \displaystyle G}$ wykresem na ${\ displaystyle S}$ , który zawiera wszystkie krawędzie w ${\ displaystyle S$ między wierzchołkami w ${\ Displaystyle S}$ ).

Aplikacje

Konstruowanie ekspanderów stałego stopnia

W 2002 roku Omer Reingold, Salil Vadhan i Avi Wigderson przedstawili prostą, wyraźną kombinatoryczną konstrukcję grafów ekspanderów o stałym stopniu. Konstrukcja jest iteracyjna i jako podstawowy element konstrukcyjny potrzebuje pojedynczego ekspandera o stałym rozmiarze. W każdej iteracji iloczyn zygzakowaty jest używany do generowania kolejnego grafu, którego rozmiar jest zwiększany, ale jego stopień i rozszerzenie pozostają niezmienione. Proces ten trwa, dając dowolnie duże ekspandery.

Ze wspomnianych powyżej właściwości iloczynu zygzakowatego widzimy, że iloczyn dużego grafu z małym wykresem dziedziczy rozmiar podobny do dużego wykresu i stopień podobny do małego wykresu, zachowując jednocześnie swoje właściwości ekspansji z obu, a zatem umożliwiające zwiększenie rozmiaru ekspandera bez szkodliwych skutków.

Rozwiązanie problemu nieskierowanej łączności st w przestrzeni logarytmicznej

W 2005 roku Omer Reingold przedstawił algorytm, który rozwiązuje problem nieskierowanej łączności st , problem testowania, czy istnieje ścieżka między dwoma danymi wierzchołkami w grafie nieskierowanym, używając tylko przestrzeni logarytmicznej. Algorytm w dużym stopniu opiera się na produkcie zygzakowatym.

Z grubsza mówiąc, aby rozwiązać problem nieskierowanej łączności st w przestrzeni logarytmicznej, graf wejściowy jest przekształcany za pomocą kombinacji zasilania i iloczynu zygzakowatego w graf regularny o stałym stopniu i średnicy logarytmicznej. Iloczyn mocy zwiększa rozszerzenie (a tym samym zmniejsza średnicę) kosztem zwiększenia stopnia, a iloczyn zygzakowaty służy do zmniejszenia stopnia przy zachowaniu rozszerzenia.

Zobacz też

Operacje na wykresach

Reingold, O .; Vadhan, S .; Wigderson, A. (2000), „Fale entropii, iloczyn wykresu zygzakowatego oraz nowe ekspandery i ekstraktory o stałym stopniu”, Proc. 41. sympozjum IEEE na temat podstaw informatyki (FOCS) , s. 3–13, arXiv : math/0406038 , doi : 10.1109/SFCS.2000.892006 .
Reingold, O (2008), „Nieukierunkowana łączność w przestrzeni dziennika”, Journal of the ACM , 55 (4): Artykuł 17, 24 strony, doi : 10.1145/1391289.1391291 .
Reingold, O .; Trevisan, L .; Vadhan, S. (2006), „Pseudolosowe spacery po regularnych dwuznakach i problem RL vs. L”, Proc. 38th ACM Symposium on Theory of Computing (STOC) , s. 457–466, doi : 10.1145/1132516.1132583 .