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

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

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

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

Определение

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

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

1. [math]\displaystyle{ (a',i') = \mathrm{Rot}_{H} (a,i) }[/math].
2. [math]\displaystyle{ (w,b')=\mathrm{Rot}_{G}(v,a') }[/math].
3. [math]\displaystyle{ (b,j')=\mathrm{Rot}_{H}(b',j) }[/math].
4. [math]\displaystyle{ \gt \mathrm{Rot}_{G \circ H}((v,a),(i,j)) =((w,b),(j',i')) }[/math].

Свойства

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

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

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

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

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

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

Пусть [math]\displaystyle{ G_{1} }[/math] — [math]\displaystyle{ (N_{1},D_{1},\lambda_{1}) }[/math] и [math]\displaystyle{ G_{2} }[/math] — [math]\displaystyle{ (D_{1},D_{2},\lambda_{2}) }[/math] — два графа, тогда [math]\displaystyle{ G \circ {z} H }[/math] является графом [math]\displaystyle{ (N_{1}\cdot D_{1},D_{2}^{2},f(\lambda_{1},\lambda_{2})) }[/math], где [math]\displaystyle{ f(\lambda_{1},\lambda_{2})\lt \lambda_{1}+\lambda_{2}+\lambda_{2}^{2}) }[/math].

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

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

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

Приложения

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

В 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.