Зигзагообразный продукт

Бинарная операция в теории графов

В теории графов зигзагообразное произведение регулярных графов , обозначаемое как , является бинарной операцией , которая берет большой граф ( ) и малый граф ( ) и производит граф, который приблизительно наследует размер большого, но степень малого. Важным свойством зигзагообразного произведения является то, что если является хорошим расширителем , то расширение полученного графа лишь немного хуже расширения . ${\displaystyle G,H}$ ${\displaystyle G\circ H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$

Грубо говоря, зигзагообразное произведение заменяет каждую вершину копией (облаком) и соединяет вершины, перемещаясь на небольшой шаг (зигзаг) внутри облака, затем на большой шаг (заг) между двумя облаками и, наконец, выполняет еще один небольшой шаг внутри целевого облака. ${\displaystyle G\circ H}$ ${\displaystyle G}$ ${\displaystyle H}$

Произведение зигзага было введено Рейнгольдом, Вадханом и Вигдерсоном (2000). Когда произведение зигзага было впервые введено, оно использовалось для явного построения экспандеров и экстракторов постоянной степени. Позднее произведение зигзага использовалось в теории вычислительной сложности для доказательства того, что симметричное логпространство и логпространство равны (Рейнгольд 2008).

Определение

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

1. Позволять . ${\displaystyle (a',i')=\mathrm {Rot} _{H}(a,i)}$
2. Позволять . ${\displaystyle (w,b')=\mathrm {Rot} _{G}(v,a')}$
3. Позволять . ${\displaystyle (b,j')=\mathrm {Rot} _{H}(b',j)}$
4. Выход . ${\displaystyle ((w,b),(j',i'))}$

Характеристики

Снижение степени

Из определения зигзагообразного произведения сразу следует, что оно преобразует граф в новый граф, который является -регулярным. Таким образом, если значительно больше , зигзагообразное произведение уменьшит степень . Грубо говоря, усиливая каждую вершину в облако размера произведения, фактически разделяет ребра каждой исходной вершины между вершинами облака, которые ее заменяют. ${\displaystyle G}$ ${\displaystyle d^{2}}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle H}$

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

Расширение графа можно измерить его спектральной щелью , при этом важным свойством зигзагообразного произведения является сохранение спектральной щели. То есть, если является «достаточно хорошим» расширителем (имеет большую спектральную щель), то расширение зигзагообразного произведения близко к исходному расширению . ${\displaystyle H}$ ${\displaystyle G}$

Формально: Определим -граф как любой -регулярный граф на вершинах, второе по величине собственное значение (соответствующего случайного блуждания) которого имеет абсолютное значение не более . ${\displaystyle (N,D,\lambda )}$ ${\displaystyle D}$ ${\displaystyle N}$ ${\displaystyle \lambda }$

Пусть будет -графом и -графом , тогда будет -графом, где . ${\displaystyle G_{1}}$ ${\displaystyle (N_{1},D_{1},\lambda _{1})}$ ${\displaystyle G_{2}}$ ${\displaystyle (D_{1},D_{2},\lambda _{2})}$ ${\displaystyle G_{1}\circ G_{2}}$ ${\displaystyle (N_{1}\cdot D_{1},D_{2}^{2},f(\lambda _{1},\lambda _{2}))}$ ${\displaystyle f(\lambda _{1},\lambda _{2})<\lambda _{1}+\lambda _{2}+\lambda _{2}^{2}}$

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

Зигзагообразное произведение действует отдельно на каждый связанный компонент . ${\displaystyle G\circ H}$ ${\displaystyle G}$

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

Приложения

Строительство расширителей постоянной степени

В 2002 году Омер Рейнгольд, Салил Вадхан и Ави Вигдерсон дали простую, явную комбинаторную конструкцию графов-расширителей постоянной степени. Конструкция итеративная и требует в качестве базового строительного блока один расширитель постоянного размера. В каждой итерации зигзагообразное произведение используется для генерации другого графа, размер которого увеличивается, но его степень и расширение остаются неизменными. Этот процесс продолжается, давая произвольно большие расширители.

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

Решение проблемы ненаправленной связности st в логарифмическом пространстве

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

Грубо говоря, для решения ненаправленной проблемы связности st в логарифмическом пространстве входной граф преобразуется с помощью комбинации степенного и зигзагообразного произведения в регулярный граф постоянной степени с логарифмическим диаметром. Степенное произведение увеличивает расширение (следовательно, уменьшает диаметр) ценой увеличения степени, а зигзагообразное произведение используется для уменьшения степени при сохранении расширения.

Смотрите также

• Графические операции

Ссылки

• Рейнгольд, О.; Вадхан , С.; Вигдерсон , А. (2000), «Волны энтропии, произведение зигзагообразных графов и новые расширители и экстракторы постоянной степени», Труды 41-го симпозиума IEEE по основам компьютерной науки (FOCS) , стр. 3–13, arXiv : math/0406038 , doi :10.1109/SFCS.2000.892006.
• Рейнгольд, О. (2008), «Ненаправленная связность в лог-пространстве», Журнал ACM , 55 (4): Статья 17, 24 страницы, doi : 10.1145/1391289.1391291.
• Рейнгольд, О.; Тревизан , Л.; Вадхан , С. (2006), «Псевдослучайные блуждания на регулярных орграфах и проблема RL против L», Труды 38-го симпозиума ACM по теории вычислений (STOC) , стр. 457–466, doi :10.1145/1132516.1132583.