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

В теория графов, то зигзагообразный продукт из регулярные графики ${ 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] раз [D]}$ чья карта вращения ${ displaystyle mathrm {Rot} _ {G circ H}}$ как следует:
${ Displaystyle mathrm {Rot} _ {G circ H} ((v, a), (i, j))}$ :

Позволять ${ Displaystyle (а ', я') = mathrm {Rot} _ {H} (а, я)}$ .
Позволять ${ Displaystyle (ш, Ь ') = mathrm {Rot} _ {G} (v, а')}$ .
Позволять ${ displaystyle (b, j ') = mathrm {Rot} _ {H} (b', j)}$ .
Выход ${ Displaystyle ((вес, Ь), (дж ', я'))}$ .

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

Понижение степени

Из определения зигзагообразного произведения следует, что оно преобразует граф ${ 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 substeq [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 году Омер Рейнгольд, Салил Вадхан и Ави Вигдерсон дали простую явную комбинаторную конструкцию расширяющих графов постоянной степени. Конструкция является итеративной и требует в качестве базового строительного блока одного расширителя постоянного размера. На каждой итерации зигзагообразное произведение используется для создания другого графа, размер которого увеличивается, но его степень и расширение остаются неизменными. Этот процесс продолжается, давая произвольно большие расширители.

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

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

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

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

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

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