Русская Википедия:Зигзаг-произведение
В теории графов зигзаг-произведение регулярных графов <math>G,H</math> (обозначается <math>G \circ H</math>) берёт большой граф <math>G</math> и маленький граф <math>H</math> и создаёт граф, примерно наследующий размер большого графа, но степень малого. Важным свойством зигзаг-произведения является то, что для хорошего экспандера <math>H</math> распространение результирующего графа лишь слегка хуже распространения графа <math>G</math>.
Грубо говоря, зигзаг-произведение <math>G \circ H</math> заменяет каждую вершину графа <math>G</math> копией (облаком) графа <math>H</math> и соединяет вершины, делая малый шаг (zig) внутри облака, а затем большой шаг (zag) между двумя облаками, и ещё один малый шаг внутри конечного облака.
Зигзаг-произведение введено Рейнгольдом, Вадханом и ВигдерсономШаблон:Sfn. Зигзаг-произведение первоначально использовалось для явного конструирования экспандеров и экстракторов постоянной степени. Позднее зигзаг-произведение использовано в теории вычислительной сложности для доказательства равенства Шаблон:Нп5 и Шаблон:Нп5[1].
Определение
Пусть <math>G</math> — <math>D</math>-регулярный граф над <math>[N]</math> c поворотом <math>\mathrm{Rot}_G</math>, и пусть <math>H</math> — <math>d</math>-регулярный граф над <math>[D]</math> c отображение ротации <math>\mathrm{Rot}_H</math>.
Зигзаг-произведение <math>G \circ H</math> определяется как <math>d^{2}</math>-регулярный граф над <math>[N] \times [D]</math>, поворот <math>\mathrm{Rot}_{G \circ H}</math> которого определяется следующим образом:
<math>\mathrm{Rot}_{G \circ H}((v,a),(i,j))</math>:
- <math>(a',i') = \mathrm{Rot}_{H} (a,i)</math>.
- <math>(w,b')=\mathrm{Rot}_{G}(v,a')</math>.
- <math>(b,j')=\mathrm{Rot}_{H}(b',j)</math>.
- <math>>\mathrm{Rot}_{G \circ H}((v,a),(i,j)) =((w,b),(j',i'))</math>.
Свойства
Уменьшение степени
Непосредственно из определения зигзаг-произведения следует, что граф <math>G</math> преобразуется в новый <math>d^{2}</math> -регулярный граф. Таким образом, если <math>G</math> существенно больше чем <math>H</math>, зигзаг-произведение уменьшает степень графа <math>G</math>.
Грубо говоря, зигзаг-произведение превращает каждую вершину графа <math>G</math> в облако размера графа <math>H</math> и распределяет дуги каждой исходной вершины по вершинам облака, заменившего её.
Сохранение спектрального зазора
Распространение графа может быть измерено его спектральным зазором. Важным свойством зигзаг-произведения является сохранение спектрального зазора. Таким образом, если <math>H</math> «достаточно хороший» экспандер (имеет большой спектральный зазор), то распространение зигзаг-произведения близко к исходному распространению графа <math>G</math>.
Формально: определяется <math>(N,D,\lambda)</math> как любой <math>D</math> -регулярный граф с <math>N</math> вершинами, у которого второе по величине собственное значение имеет абсолютное значение как минимум <math>\lambda</math>.
Пусть <math>G_{1}</math> — <math>(N_{1},D_{1},\lambda_{1})</math> и <math>G_{2}</math> — <math>(D_{1},D_{2},\lambda_{2})</math> — два графа, тогда <math>G \circ {z} H</math> является графом <math>(N_{1}\cdot D_{1},D_{2}^{2},f(\lambda_{1},\lambda_{2}))</math>, где <math>f(\lambda_{1},\lambda_{2})<\lambda_{1}+\lambda_{2}+\lambda_{2}^{2})</math>.
Сохранение связности
Зигзаг-произведение <math>G \circ H</math> работает отдельно для каждой компоненты связности графа <math>G</math>.
Формально: пусть даны два графа: <math>G</math> — <math>D</math>-регулярный граф над <math>[N]</math> и <math>H</math> — <math>d</math>-регулярный граф над <math>[D]</math>. Если <math>S\subseteq[N]</math> является компонентой связности графа <math>G</math>, то <math>G|_{S} \circ H=G\circ H|_{S\times D}</math>, где <math>G|_{S}</math> — подграф графа <math>G</math>, образованный вершинами <math>S</math> (то есть граф над <math>S</math>, содержащий все дуги из <math>G</math> между вершинами из <math>S</math>).
Приложения
Конструирование экспандеров постоянной степени
В 2002 году Омер Рейнгольд, Салил Вадхан и Ави ВидгерсонШаблон:Sfn показали простое явное комбинаторное конструирование экспандеров постоянной степени. Конструирование производится итеративно и требует в качестве базиса экспандер постоянной степени. На каждой итерации используется зигзаг-произведение для создания другого графа, чей размер увеличивается, но степень и распространение остаются неизменными. Повторение процесса позволяет создать произвольно большие экспандеры.
Решение ненаправленной s-t задачи связности в логарифмическом пространстве памяти
В 2005 году Омер Рейнгольд представил алгоритм решения задачи st-связности, использующий логарифмическое пространство памяти. Задача состоит в проверке, существует ли путь между двумя заданными вершинами ненаправленного графа. Алгоритм сильно опирается на зигзаг-произведение.
Грубо говоря, для решения ненаправленной задачи s-t связности в логарифмическом пространстве памяти исходный граф преобразуется с использованием комбинации произведения и зигзаг-произведения в регулярный граф постоянной степени с логарифмическим диаметром. Произведение увеличивает распространение (ввиду увеличения диаметра) за счёт увеличения степени, а зигзаг-произведение используется для уменьшения степени с сохранением распространения.
См. также
Примечания
Литература
