Зигзаг-произведение

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

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

Зигзаг-произведение введено Рейнгольдом, Вадханом и Вигдерсоном. Зигзаг-произведение первоначально использовалось для явного конструирования экспандеров и экстракторов постоянной степени. Позднее зигзаг-произведение использовано в теории вычислительной сложности для доказательства равенства SL и L.

Определение

Пусть $G$ — $D$-регулярный граф над $[N]$ c поворотом $\mathrm {Rot} _{G}$, и пусть $H$ — $d$-регулярный граф над $[D]$ c отображение ротации $\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))$:

1. $(a',i')=\mathrm {Rot} _{H}(a,i)$.
2. $(w,b')=\mathrm {Rot} _{G}(v,a')$.
3. $(b,j')=\mathrm {Rot} _{H}(b',j)$.
4. $>\mathrm {Rot} _{G\circ H}((v,a),(i,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\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})$.

Сохранение связности

Зигзаг-произведение $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 году Омер Рейнгольд, Салил Вадхан и Ави Видгерсон показали простое явное комбинаторное конструирование экспандеров постоянной степени. Конструирование производится итеративно и требует в качестве базиса экспандер постоянной степени. На каждой итерации используется зигзаг-произведение для создания другого графа, чей размер увеличивается, но степень и распространение остаются неизменными. Повторение процесса позволяет создать произвольно большие экспандеры.

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

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

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

См. также

• Операции над графами

Литература

• Omer Reingold, Salil Vadhan, Avi Wigderson. Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS). — 2000. — С. 3—13. — doi:10.1109/SFCS.2000.892006.
• Omer Reingold, Luca Trevisan, Salil Vadhan. Proc. 38th ACM Symposium on Theory of Computing (STOC). — 2006. — С. 457—466. — doi:10.1145/1132516.1132583.