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

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

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

Определение

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

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

1. ${\displaystyle (a',i')=\mathrm {Rot} _{H}(a,i)}$ .
2. ${\displaystyle (w,b')=\mathrm {Rot} _{G}(v,a')}$ .
3. ${\displaystyle (b,j')=\mathrm {Rot} _{H}(b',j)}$ .
4. ${\displaystyle >\mathrm {Rot} _{G\circ H}((v,a),(i,j))=((w,b),(j',i'))}$ .

Свойства

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

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

Грубо говоря, зигзаг-произведение превращает каждую вершину графа ${\displaystyle G}$ в облако размера графа ${\displaystyle H}$ и распределяет дуги каждой исходной вершины по вершинам облака, заменившего её.

Сохранение спектрального зазора

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

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

Пусть ${\displaystyle G_{1}}$ — ${\displaystyle (N_{1},D_{1},\lambda _{1})}$ и ${\displaystyle G_{2}}$ — ${\displaystyle (D_{1},D_{2},\lambda _{2})}$ — два графа, тогда ${\displaystyle G\circ {z}H}$ является графом ${\displaystyle (N_{1}\cdot D_{1},D_{2}^{2},f(\lambda _{1},\lambda _{2}))}$ , где ${\displaystyle f(\lambda _{1},\lambda _{2})<\lambda _{1}+\lambda _{2}+\lambda _{2}^{2})}$ .

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

Зигзаг-произведение ${\displaystyle G\circ H}$ работает отдельно для каждой компоненты связности графа ${\displaystyle G}$ .

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

Приложения

Конструирование экспандеров постоянной степени

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

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

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

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

См. также

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

Примечания

Литература

• Omer Reingold, Salil Vadhan, Avi Wigderson. Proc. 41st IEEE (FOCS). — 2000. — С. 3—13 . — doi : .
• Omer Reingold, Luca Trevisan, Salil Vadhan. . — 2006. — С. 457—466 . — doi : .