Карта вращения

Не путать с Вращением (математика) .

В математике карта вращения — это функция, которая представляет собой неориентированный граф с метками ребер , где каждая вершина перечисляет своих исходящих соседей. Карты вращения были впервые представлены Рейнгольдом, Вадханом и Вигдерсоном («Волны энтропии, произведение зигзагообразного графа и новые расширители постоянной степени», 2002) для удобного определения зигзагообразного произведения и доказательства его свойств. Дана вершина $v$ и метка края $i$, карта вращения возвращает $i$'й сосед $v$ и метка края, ведущая обратно к $v$.

Определение

Для D -регулярного графа G карта вращения $\mathrm {Rot} _{G}:[N]\times [D]\rightarrow [N]\times [D]$ определяется следующим образом: $\mathrm {Rot} _{G}(v,i)=(w,j)$ если i -е ребро, выходящее из v, ведет в w , а j -е ребро, выходящее из w, ведет в v .

Основные свойства

Из определения мы видим, что $\mathrm {Rot} _{G}$ является перестановкой, и более того $\mathrm {Rot} _{G}\circ \mathrm {Rot} _{G}$ это карта идентичности ( $\mathrm {Rot} _{G}$ это инволюция ).

Особые случаи и свойства

• Карта вращения последовательно помечена, если все ребра, выходящие из каждой вершины, помечены таким образом, что в каждой вершине метки всех входящих ребер различны. Каждый регулярный граф имеет некую согласованную маркировку.
• Согласованная карта вращения может использоваться для кодирования квантового блуждания в дискретном времени на (регулярном) графе.
• Карта вращения — это $\pi$-последовательно, если $\forall v\ \mathrm {Rot} _{G}(v,i)=(v[i],\pi (i))$. Из определения, А. $\pi$-последовательная карта вращения имеет последовательные метки.

См. также

• Зигзагообразное изделие
• Система вращения

Ссылки

• Рейнгольд, О.; Вадхан, С.; Видгерсон, А. (2000). «Волны энтропии, произведение зигзагообразного графа и новые расширители и экстракторы постоянной степени». Материалы 41-го ежегодного симпозиума по основам информатики . стр. 3–13. arXiv : math/0406038 . дои : 10.1109/SFCS.2000.892006 . ISBN  978-0-7695-0850-4 . S2CID   420651 .

• Рейнгольд, О. (2008), «Ненаправленная связность в пространстве журналов», Журнал ACM , 55 (4): 1–24, doi : 10.1145/1391289.1391291 , S2CID   207168478

• Рейнгольд, О.; Тревизан, Л.; Вадхан, С. (2006), «Псевдослучайные блуждания по регулярным орграфам и проблема RL против L», Труды тридцать восьмого ежегодного симпозиума ACM по теории вычислений , стр. 457–466, doi : 10.1145/1132516.1132583 , ISBN  978-1595931344 , S2CID   17360260

• Александр, К. (2021), Примечание о согласованных картах вращения графовых декартовых произведений , doi : 10.13140/RG.2.2.19721.57446

• Александр, К. (2021), Согласованные карты вращения вызывают унитарный оператор сдвига в квантовых блужданиях дискретного времени , doi : 10.13140/RG.2.2.17614.59201