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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Определение[править | править вики-текст]

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

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

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

Свойства[править | править вики-текст]

Уменьшение степени[править | править вики-текст]

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

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Reingold, Vadhan, Wigderson, 2000, p. 3—13
  2. Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — С. 24. — DOI:10.1145/1391289.1391291.
  3. Reingold, Vadhan, Wigderson, 2000

Литература[править | править вики-текст]