Зигзагообразное изделие

В теории графов зигзагообразное произведение графов правильных $G,H$ , обозначенный $G\circ H$ , — это бинарная операция , которая обрабатывает большой граф ( $G$ ) и небольшой график ( $H$ ) и создает граф, который примерно наследует размер большого графа, но степень маленького. Важным свойством зигзагообразного произведения является то, что если $H$ является хорошим расширителем , то расширение полученного графа лишь немногим хуже, чем расширение $G$ .

Грубо говоря, зигзагообразное произведение $G\circ H$ заменяет каждую вершину $G$ с копией (облаком) $H$ , и соединяет вершины, перемещая небольшой шаг (зиг) внутри облака, за которым следует большой шаг (заг) между двумя облаками, и, наконец, выполняет еще один небольшой шаг внутри целевого облака.

Зигзагообразное произведение было предложено Рейнгольдом , Вадханом и Вигдерсоном (2000) . Когда зигзагообразное произведение было впервые представлено, оно использовалось для явного построения расширителей и экстракторов постоянной степени. Позже зигзагообразное произведение было использовано в теории сложности вычислений, чтобы доказать, что симметричное лог-пространство и лог-пространство равны ( Reingold 2008 ).

Определение

Позволять $G$ быть $D$ -регулярный график на $[N]$ с картой вращения $\mathrm {Rot} _{G}$ и пусть $H$ быть $d$ -регулярный график на $[D]$ с картой вращения $\mathrm {Rot} _{H}$ . Зигзагообразное изделие $G\circ H$ определяется как $d^{2}$ -регулярный график на $[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)$ .
Выход $((w,b),(j',i'))$ .

Характеристики

Понижение степени

Из определения зигзагообразного произведения сразу следует, что оно преобразует граф $G$ к новому графику, который $d^{2}$ -обычный. Таким образом, если $G$ значительно больше, чем $H$ , зигзагообразное произведение уменьшит степень $G$ . Грубо говоря, усиливая каждую вершину $G$ в облако размером $H$ продукт фактически разделяет ребра каждой исходной вершины между вершинами облака, которые ее заменяют.

Сохранение спектральной щели

Расширение графа можно измерить по его спектральному разрыву , причем важным свойством зигзагообразного произведения является сохранение спектрального разрыва. То есть, если $H$ является «достаточно хорошим» расширителем (имеет большую спектральную щель), то разложение зигзагообразного произведения близко к исходному разложению $G$ .

Формально: Определите $(N,D,\lambda )$ -график как любой $D$ -регулярный график на $N$ вершины, второе по величине собственное значение (соответствующего случайного блуждания) имеет не более чем абсолютное значение $\lambda$ .

Позволять $G_{1}$ быть $(N_{1},D_{1},\lambda _{1})$ -график и $G_{2}$ быть $(D_{1},D_{2},\lambda _{2})$ -график, тогда $G_{1}\circ G_{2}$ это $(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}$ .

Сохранение подключения

Зигзагообразное изделие $G\circ H$ работает отдельно на каждом подключенном компоненте $G$ .

Формально говоря, даны два графика: $G$ , а $D$ -регулярный график на $[N]$ и $H$ , а $d$ -регулярный график на $[D]$ - если $S\subseteq [N]$ является связной компонентой $G$ затем $G|_{S}\circ H=G\circ H|_{S\times D}$ , где $G|_{S}$ является подграфом $G$ вызванный $S$ (т.е. график на $S$ который содержит все ребра из $G$ между вершинами в $S$ ).

Приложения

Конструкция расширителей постоянной степени

В 2002 году Омер Рейнгольд, Салил Вадхан и Ави Вигдерсон предложили простую и явную комбинаторную конструкцию графов-расширителей постоянной степени. Построение является итеративным, и в качестве базового строительного блока требуется один расширитель постоянного размера. На каждой итерации зигзагообразное произведение используется для создания другого графа, размер которого увеличивается, но его степень и расширение остаются неизменными. Этот процесс продолжается, приводя к появлению сколь угодно больших расширителей.

Из свойств зигзагообразного произведения, упомянутых выше, мы видим, что произведение большого графа на маленький граф наследует размер, аналогичный большому графу, и степень, аналогичную маленькому графу, сохраняя при этом свои свойства расширения от обоих, таким образом позволяющий увеличить размер расширителя без вредных последствий.

Решение задачи ненаправленной связности st в логарифмическом пространстве

В 2005 году Омер Рейнгольд представил алгоритм, который решает ненаправленную проблему st-связности , проблему проверки наличия пути между двумя заданными вершинами в неориентированном графе, используя только логарифмическое пространство. Алгоритм в значительной степени опирается на зигзагообразное произведение.

Грубо говоря, чтобы решить ненаправленную задачу связности st в логарифмическом пространстве, входной граф преобразуется с помощью комбинации возведения в степень и зигзагообразного произведения в регулярный граф постоянной степени с логарифмическим диаметром. Произведение мощности увеличивает расширение (следовательно, уменьшает диаметр) за счет увеличения степени, а зигзагообразное произведение используется для уменьшения степени при сохранении расширения.

См. также

Операции с графами

Ссылки

Рейнгольд, О. ; Вадхан, С. ; Вигдерсон, А. (2000), «Волны энтропии, произведение зигзагообразного графа и новые расширители и экстракторы постоянной степени», Proc. 41-й симпозиум IEEE по основам компьютерных наук (FOCS) , стр. 3–13, arXiv : math/0406038 , doi : 10.1109/SFCS.2000.892006 .
Рейнгольд, О. (2008), «Ненаправленная связность в пространстве журналов», Журнал ACM , 55 (4): Статья 17, 24 страницы, doi : 10.1145/1391289.1391291 .
Рейнгольд, О. ; Тревизан, Л .; Вадхан, С. (2006), «Псевдослучайные блуждания по регулярным орграфам и проблема RL против L», Proc. 38-й симпозиум ACM по теории вычислений (STOC) , стр. 457–466, doi : 10.1145/1132516.1132583 .