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

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

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

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

Определение

Пусть  — -регулярный граф над c поворотом , и пусть  — -регулярный граф над c отображение ротации .

Зигзаг-произведение определяется как -регулярный граф над , поворот которого определяется следующим образом:
:

  1. .
  2. .
  3. .
  4. .

Свойства

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

Непосредственно из определения зигзаг-произведения следует, что граф преобразуется в новый -регулярный граф. Таким образом, если существенно больше чем , зигзаг-произведение уменьшает степень графа .

Грубо говоря, зигзаг-произведение превращает каждую вершину графа в облако размера графа и распределяет дуги каждой исходной вершины по вершинам облака, заменившего её.

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

Распространение графа может быть измерено его спектральным зазором. Важным свойством зигзаг-произведения является сохранение спектрального зазора. Таким образом, если «достаточно хороший» экспандер (имеет большой спектральный зазор), то распространение зигзаг-произведения близко к исходному распространению графа .

Формально: определяется как любой -регулярный граф с вершинами, у которого второе по величине собственное значение имеет абсолютное значение как минимум .

Пусть  — и  —  — два графа, тогда является графом , где .

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

Зигзаг-произведение работает отдельно для каждой компоненты связности графа .

Формально: пусть даны два графа:  — -регулярный граф над и  — -регулярный граф над . Если является компонентой связности графа , то , где  — подграф графа , образованный вершинами (то есть граф над , содержащий все дуги из между вершинами из ).

Приложения

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

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

Литература

  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.