В теории графов зигзаг-произведение регулярных графов (обозначается ) берёт большой граф и маленький граф и создаёт граф, примерно наследующий размер большого графа, но степень малого. Важным свойством зигзаг-произведения является то, что для хорошего экспандера распространение результирующего графа лишь слегка хуже распространения графа .
Грубо говоря, зигзаг-произведение заменяет каждую вершину графа копией (облаком) графа , и соединяет вершины, делая малый шаг (zig) внутри облака, а затем большой шаг (zag) между двумя облаками, и еще один малый шаг внутри конечного облака.
Зигзаг-произведение было введено Рейнгольдом, Вадханом и Вигдерсоном (Reingold, Vadhan, Wigderson, 2000) [1]. Когда зигзаг-произведение было придумано, оно использовалось для явного конструирования экспандеров и экстракторов постоянной степени. Позднее зигзаг-произведение было использовано в теории вычислительной сложности для доказательства равенства SL и L [2].
Пусть – -регулярный граф над c поворотом и пусть – -регулярный граф над c отображение ротации .
Зигзаг-произведение определяется как -регулярный граф над , поворот которого определяется следующим образом:
:
Непосредственно из определения зигзаг-произведения следует, что граф преобразуется в новый -регулярный граф. Таким образом, если существенно больше чем , зигзаг-произведение уменьшает степень графа .
Грубо говоря, зигзаг-произведение превращает каждую вершину графа в облако размера графа и распределяет дуги каждой исходной вершины по вершинам облака, заменившего её.
Распространение графа может быть измерено его спектральным зазором. Важным свойством зигзаг-произведения является сохранение спектрального зазора. Таким образом, если “достаточно хороший” экспандер (имеет болшой спектральный зазор), то распространение зигзак-произведения близко к исходному распространению графа .
Формально: Определим как любой -регулярный граф с вершинами, у которого второе по величине собственное значение имеет абсолютное значение как минимум .
Пусть – и – – два графа, тогда является графом , где .
Зигзаг-произведение работает отдельно для каждой компоненты связности графа .
Формально. Пусть даны два графа: – -регулярный граф над и – -регулярный граф над . Если является компонентой связности графа , то , где – подграф графа , образованный вершинами (то есть, граф над , содержащий все дуги из между вершинами из ).
В 2002-м году Омер Рейнгольд, Салил Вадхан и Ави Видгерсон (Omer Reingold, Salil Vadhan, Avi Wigderson) показали простое явное комбинаторное конструирование экспандеров постоянной степени. Конструирование производится итеративно и требует в качестве базиса экспандер постоянной степени. На каждой итерации используется зигзаг-произведение для создания другого графа, чей размер увеличивается, но степень и распространение остаются неизменными. Повторение процесса позволяет создать произвольно большие экспандеры.
В 2005-м году Омер Рейнгольд представил алгоритм решения задачи st-связности, использующий логарифмическое пространство памяти. Задача состоит в проверке, существует ли путь между двумя заданными вершинами ненаправленного графа. Алгоритм сильно опирается на зигзаг-произведение.
Грубо говоря, для решения ненаправленной задачи s-t связности в логарифмическом пространстве памяти исходный граф преобразуется с использованием комбинации произведения и зигзаг-произведения в регулярный граф постоянной степени с логарифмическим диаметром. Произведение увеличивает распространение (ввиду увеличения диаметра) за счёт увеличения степени, а зигзаг-произведение используется для уменьшения степени с сохранением распространения.
Зигзаг-произведение.