回転マップ

数学において、回転マップは、各頂点がその出ている隣接頂点を列挙する、無向辺ラベル付きグラフを表す関数です。回転マップは、ジグザグ積を簡便に定義し、その性質を証明するために、Reingold、Vadhan、Wigderson（「エントロピー波、ジグザググラフ積、および新しい定数次数エクスパンダー」、2002年）によって初めて導入されました。${\displaystyle v}$エッジラベル${\displaystyle i}$回転マップは、${\displaystyle i}$の隣人${\displaystyle v}$そしてエッジラベルは${\displaystyle v}$。

D正則グラフGの場合、回転マップ${\displaystyle \mathrm {Rot} _{G}:[N]\times [D]\rightarrow [N]\times [D]}$は次のように定義されます。${\displaystyle \mathrm {Rot} _{G}(v,i)=(w,j)}$vから出るi番目の辺がwにつながり、wから出るj番目の辺がvにつながる場合。 

定義から、${\displaystyle \mathrm {Rot} _{G}}$は順列であり、さらに${\displaystyle \mathrm {Rot} _{G}\circ \mathrm {Rot} _{G}}$は恒等写像です（${\displaystyle \mathrm {Rot} _{G}}$（これは内反である）。

• 回転マップは、各頂点から出るすべての辺に、各頂点において入ってくる辺のラベルがすべて異なるようにラベルが付けられている場合、一貫性のあるラベル付けがされていると言えます。すべての正則グラフには、何らかの一貫性のあるラベル付けが存在します。
• 一貫性のある回転マップを使用することで、（通常の）グラフ上での、独自に考案された離散時間量子ウォークを符号化することができる。
• 回転マップは${\displaystyle \pi }$-一貫性がある場合${\displaystyle \forall v\ \mathrm {Rot} _{G}(v,i)=(v[i],\pi (i))}$定義から、${\displaystyle \pi }$-一貫した回転マップには一貫したラベルが付けられています。

• ジグザグ製品
• 回転システム