Mapa rotacji

W matematyce mapa rotacji jest funkcją reprezentującą nieskierowany graf oznaczony krawędzią , w którym każdy wierzchołek wylicza wychodzących sąsiadów. Mapy rotacyjne zostały po raz pierwszy wprowadzone przez Reingolda, Vadhana i Wigdersona („Entropywaves, the zig-zag graph product, and new fixed- degree expanders”, 2002) w celu wygodnego zdefiniowania iloczynu zygzakowatego i udowodnienia jego właściwości. Biorąc pod uwagę wierzchołek i etykietę krawędzi $\ displaystyle v}$ mapa obrotu zwraca $v$ ${\ displaystyle i}$ 'th sąsiad z ${\ displaystyle v}$ i etykieta krawędzi, która prowadziłaby z powrotem do ${\ displaystyle v}$ .

Definicja

Dla D -regularnego wykresu G mapa obrotu $\ Displaystyle \ operatorname {Rot} _ {G}: [N] \ razy [ D]\rightarrow [N]\times [D]}$ jest zdefiniowane następująco: ${\ Displaystyle \ operatorname {Rot} _ {G} (v, i) = (w, j)}$ jeśli i -ta krawędź wychodząca z v prowadzi do w , a j - ta krawędź wychodząca z w prowadzi do v .

Podstawowe właściwości

Z definicji widzimy, że $_ {G$ $o$ R to mapa tożsamości ( ${\ Displaystyle \ operatorname {Rot} _ {G}}$ to inwolucja ).

Przypadki specjalne i właściwości

Mapa rotacji jest konsekwentnie oznaczona, jeśli wszystkie krawędzie wychodzące z każdego wierzchołka są oznaczone w taki sposób, że w każdym wierzchołku etykiety przychodzących krawędzi są różne. Każdy regularny wykres ma pewne spójne etykietowanie.
Spójnej mapy rotacji można użyć do zakodowania wymyślonego spaceru kwantowego w czasie dyskretnym na (regularnym) wykresie.
Mapa rotacji jest $spójna$ jeśli ${\ Displaystyle \ forall v \ \ operatorname {Rot} _ {G}(v,i)=(v[i],\pi (i))}$ . Z definicji $.$ mapa rotacji jest konsekwentnie oznaczona

Zobacz też

Reingold, O.; Vadhan, S.; Widgerson, A. (2000), „Fale entropii, iloczyn wykresu zygzakowatego oraz nowe ekspandery i ekstraktory o stałym stopniu”, 41. doroczne sympozjum na temat podstaw informatyki : 3–13, arXiv : math / 0406038 , doi : 10.1109/SFCS.2000.892006 , ISBN 978-0-7695-0850-4

Reingold, O (2008), „Nieukierunkowana łączność w przestrzeni dziennika”, Journal of the ACM , 55 (4): 1–24, doi : 10.1145 / 1391289.1391291

Reingold, O.; Trevisan, L.; Vadhan, S. (2006), „Pseudolosowe spacery po regularnych digrafach i problem RL vs. L”, Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing : 457, doi : 10.1145/1132516.1132583 , ISBN 978-1595931344

Alexander , C. (2021), A Note on Consistent Rotation Maps of Graph Cartesian Products , doi : 10.13140/RG.2.2.19721.57446

Alexander, C. (2021), Consistent Rotation Maps Induce a Unitary Shift Operator in Discrete Time Quantum Walks , doi : 10.13140/RG.2.2.17614.59201