회전 지도

수학에서 회전 지도는 각 정점들이 나가는 이웃들을 열거하는 방향을 정하지 않은 가장자리 라벨 그래프를 나타내는 함수다.회전 지도는 지그재그 제품을 편리하게 정의하고 그 특성을 증명하기 위해 레이놀드, 바단, 위그더슨("엔트로피 웨이브, 지그재그 그래프 제품, 새로운 상수도 확장기", 2002년)에 의해 처음 도입되었다.정점 $v{\displaystyle }$ ${\displaystyle$ v$}$과(와$$) 에지 $레이블{\displaystyle }$ i ${\$$displaystyle i$$}$을(를) 지정하면 회전 맵은 v ${\displaystyle v}$의$$'$th번째{\displaystyle }$ 인접' 및 $v{\displaystyle }$ ${\displaystyle$ v$}$로 다시 이어지는 에지 레이블을 반환한다$.$

정의

D-정규 그래프 G의 경우 회전 지도 $R{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{o}}_{}}$ t ${\displaystyle {}_{}}$:${\displaystyle }$[ ${\displaystyle N}$ ${\displaystyle ]}$× [${\displaystyle }$D${\displaystyle ]}$ → [${\displaystyle }$N ]${\displaystyle \times }$ [ ${\displaystyle D}$ ] × [ D ${\displaystyle ]}$\표시 ${\displaystyle \mathrm{스타일}}$ \$mathrm {Rot} _{G:$$[N]\$${\displaystyle {\mathrm{time}}_{}}$$[D]\rightarrow [N]\time[N]\$time[${\displaystyle D]\}}$은(는${\displaystyle )}$ ${\displaystyle {}_{}}$과 같이 정의된다$$: v를 떠나는 i edge가 w로 이어지는$$ 경우 Ro t G${\displaystyle {}_{}}$(${\displaystyle {\mathrm{v}}_{}}$ , i ) =${\displaystyle }$( w${\displaystyle }$,${\displaystyle j}$) ${\displaysty \matrmatmatrmatrm {Rot} _{G}$ _{G}($v,i)=($는 (=(w,i)=(으)=(으)=(으$)}).$

기본 속성

From the definition we see that ${\displaystyle \mathrm {Rot} _{G}}$ is a permutation, and moreover ${\displaystyle \mathrm {Rot} _{G}\circ \mathrm {Rot} _{G}}$ is the identity map (${\displaystyle \mathrm {Rot} _{G}}$ is an involution).

특수 사례 및 속성

• 회전 지도는 각 정점을 나가는 모든 가장자리가 각 꼭지점에서 들어오는 가장자리의 라벨이 모두 구별되는 방식으로 라벨링되는 경우 일관되게 라벨링된다.모든 정규 그래프에는 일정한 라벨이 붙어 있다.
• 일관된 회전 맵을 사용하여 (정규) 그래프의 새로운 이산 시간 양자 워크를 인코딩할 수 있다.
• A rotation map is ${\displaystyle \pi }$-consistent if ${\displaystyle \forall v\ \mathrm {Rot} _{G}(v,i)=(v[i],\pi (i))}$. From the definition, a ${\displaystyle \pi }$-consistent rotation map is consistently labeled.

참고 항목

• 지그재그 제품
• 회전계통

참조