Cik-cak produkt - Zig-zag product
v teorie grafů, cik-cak produkt z pravidelné grafy , označeno , vezme velký graf () a malý graf () a vytvoří graf, který přibližně zdědí velikost velkého, ale stupeň malého. Důležitou vlastností produktu cik-cak je, že pokud je dobrý expandér, pak je expanze výsledného grafu jen o něco horší než expanze .
Zhruba řečeno, cik-cak produkt nahradí každý vrchol s kopií (mrakem) z , a spojuje vrcholy pohybem malého kroku (zig) uvnitř mraku, následovaného velkým krokem (zag) mezi dvěma mraky a nakonec provede další malý krok uvnitř cílového mraku.
Produkt cikcak byl představen společností Reingold, Vadhan a Wigderson (2000). Když byl produkt cik-cak poprvé představen, byl použit pro explicitní konstrukci expandérů a extraktorů stálého stupně. Později byl produkt cik-cak použit v teorie výpočetní složitosti dokázat to symetrický logický prostor a logický prostor jsou rovny (Reingold 2008 ).
Definice
Nechat být -pravidelný graf na s rotační mapa a nechte být -pravidelný graf na s rotační mapou Cik-cak produkt je definován jako -pravidelný graf na jehož rotační mapa je následující:
:
- Nechat .
- Nechat .
- Nechat .
- Výstup .
Vlastnosti
Snížení stupně
Z definice cikcakového produktu je okamžité, že transformuje graf do nového grafu, který je -pravidelný. Tedy pokud je podstatně větší než , cikcak produkt sníží stupeň . Zhruba řečeno, zesílením každého vrcholu do oblaku o velikosti produkt ve skutečnosti rozděluje okraje každého původního vrcholu mezi vrcholy mraku, které jej nahrazují.
Zachování spektrální mezery
Roztažnost grafu lze měřit podle jeho spektrální mezera, s důležitou vlastností produktu cikcak, zachování spektrální mezery. To je, pokud je „dostatečně dobrý“ expandér (má velkou spektrální mezeru), pak se expanze cikcakového produktu blíží původnímu rozšíření .
Formálně: Definujte a -graf jako každý -pravidelný graf na vrcholy, jejichž druhé největší vlastní číslo (přidružené náhodné chůze) má maximálně absolutní hodnotu .
Nechat být -graf a být - tedy graf je -graf, kde .
Zachování konektivity
Cikcak produkt pracuje samostatně na každé připojené komponentě .
Formálně vzato, vzhledem ke dvěma grafům: , a -pravidelný graf na a , a -pravidelný graf na - pokud je připojenou součástí pak , kde je podgrafem vyvolané (tj. graf na který obsahuje všechny hrany v mezi vrcholy v ).
Aplikace
Konstrukce expandérů stálého stupně
V roce 2002 Omer Reingold, Salil Vadhan a Avi Wigderson poskytli jednoduchou, explicitní kombinatorickou konstrukci expandujících grafů konstantního stupně. Konstrukce je iterativní a jako základní stavební blok potřebuje jediný expandér konstantní velikosti. V každé iteraci se produkt cikcak používá k vygenerování dalšího grafu, jehož velikost se zvětší, ale jeho stupeň a expanze zůstanou nezměněny. Tento proces pokračuje a poskytuje libovolně velké expandéry.
Z výše zmíněných vlastností cikcakového produktu vidíme, že produkt velkého grafu s malým grafem, zdědí velikost podobnou velkému grafu a stupeň podobný malému grafu, při zachování jeho expanzních vlastností z obou, tedy což umožňuje zvětšit velikost expandéru bez škodlivých účinků.
Řešení problému s nepřímým připojením s-t v logaritmickém prostoru
V roce 2005 představil Omer Reingold algoritmus, který řeší neorientované st-konektivita problém, problém testování, zda existuje cesta mezi dvěma danými vrcholy v neorientovaném grafu, za použití pouze logaritmického prostoru. Algoritmus do značné míry závisí na produktu cikcak.
Zhruba řečeno, aby se vyřešil problém s neorientovanou konektivitou s-t v logaritmickém prostoru, vstupní graf se transformuje pomocí kombinace napájení a cikcakového produktu do pravidelného grafu konstantního stupně s logaritmickým průměrem. Energetický produkt zvyšuje expanzi (tedy zmenšuje průměr) za cenu zvyšování stupně a cikcak produkt se používá ke snížení stupně při zachování expanze.
Viz také
Reference
- Reingold, O.; Vadhan, S.; Wigderson, A. (2000), „Entropické vlny, produkt klikatého grafu a nové expandéry a extraktory konstantního stupně“, Proc. 41. IEEE Symposium on Foundations of Computer Science (FOCS), s. 3–13, arXiv:matematika / 0406038, doi:10.1109 / SFCS.2000.892006.
- Reingold, O (2008), „Neřízená konektivita v logovém prostoru“, Deník ACM, 55 (4): článek 17, 24 stran, doi:10.1145/1391289.1391291.
- Reingold, O.; Trevisan, L.; Vadhan, S. (2006), „Pseudonáhodné procházky po regulárních digrafech a problém RL vs. L“, Proc. 38. ACM Symposium on Theory of Computing (STOC), str. 457–466, doi:10.1145/1132516.1132583.