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

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

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

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

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

Определение[править | править исходный текст]

Пусть GD-регулярный граф над [N] c поворотом \mathrm{Rot}_G и пусть Hd-регулярный граф над [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.

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

Приложения[править | править исходный текст]

Конструирование экспандеров постоянной степени[править | править исходный текст]

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

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

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

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

Смотрите также[править | править исходный текст]

Ссылки[править | править исходный текст]

  1. 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
  2. Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — В. 4. — Т. 55. — С. Article 17, 24 pages. — DOI:10.1145/1391289.1391291

Литература[править | править исходный текст]