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

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

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

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

Определение

Пусть $G$ — $D$-регулярный граф над $[N]$ c поворотом ${\mathrm{R}\mathrm{o}\mathrm{t}}_G$, и пусть $H$ — $d$-регулярный граф над $[D]$ c отображение ротации ${\mathrm{R}\mathrm{o}\mathrm{t}}_H$.

Зигзаг-произведение $G\circ H$ определяется как $d^2$-регулярный граф над $[N]\times [D]$, поворот ${\mathrm{R}\mathrm{o}\mathrm{t}}_{G\circ H}$ которого определяется следующим образом:
${\mathrm{R}\mathrm{o}\mathrm{t}}_{G\circ H}((v,a),(i,j))$:

1. $(a^{\prime },i^{\prime })={\mathrm{R}\mathrm{o}\mathrm{t}}_H(a,i)$.
2. $(w,b^{\prime })={\mathrm{R}\mathrm{o}\mathrm{t}}_G(v,a^{\prime })$.
3. $(b,j^{\prime })={\mathrm{R}\mathrm{o}\mathrm{t}}_H(b^{\prime },j)$.
4. $>{\mathrm{R}\mathrm{o}\mathrm{t}}_{G\circ H}((v,a),(i,j))=((w,b),(j^{\prime },i^{\prime }))$.

Свойства

Уменьшение степени

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

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

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

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

См. также

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

Литература

• Шаблон:Статья
• Шаблон:Статья