Ruta más corta en aritmética modular.

Question

Supongamos que tenemos 7 vértices, cada uno de los cuales corresponde a un módulo entero diferente siete.El borde existe entre dos vértices X e Y si X + 3 ≡ Y MOD 7. Por ejemplo, hay un borde entre 0 y 3, y un borde entre 5 y 2. ¿Cuál es la longitud de la ruta más corta entre 0 y 1??

Mi método para obtener la respuesta es aplicar la definición de congruencia.El borde sale de IFF $ 7 |x + 3 - y $ .Por lo tanto, obtuve un gráfico cíclico y luego obtuve la respuesta es 2. ¿Hay algún método que pueda jugar con aritmética modular sin dibujar una gráfica para que pueda obtener la ruta más corta entre el nodo 0 y el nodo 1?

Answer 1

Consideremos el caso más general en el que tiene $ n $ vértices, y se conecta $ x, y $ si $ XY \ Equiv A \ PMOD {N} $ (en su caso, $ n= 7 $ y $ a= 3 $ ).

Tu gráfica es una unión de ciclos disjoint. Cuando $ n $ es Prime (como en su caso), es un solo ciclo. Por lo tanto, si desea obtener de $ x $ a $ y $ , ya sea que sigue agregando $ A $ (Modulo $ n $ ), de usted Mantenga la restación $ A $ (Modulo $ n $ ). Si agrega $ m $ veces el valor $ a $ (donde $ m $ es posiblemente negativo) luego $ x + ma \ equiv- \ pmod {n} $ , es decir, $ mA \ Equiv yx \ PMOD {N} $ . Supongamos ahora que $ (a, n)= 1 $ (por ejemplo, $ n $ es Prime y $ 1 \ leq A \ leq n-1 $ ). Luego $ m \ Equiv A ^ {- 1} (y-x) \ pmod {n} $ .

Resolviendo la ecuación anterior (asumiendo $ x \ no \ equiv y \ pmod {n} $ ), habrá una solución $ m _ + $ en el rango $ 1, \ ldots, n-1 $ y otro $ m _- $ en el rango $ - 1, \ ldots, - (N-1) $ . La distancia es $ \ min (M _ +, - M _-) $ .

En su caso, $ n= 7 $ y $ a= 3 $ . Podemos computar $ a ^ {- 1}= 5 $ . Si $ x= 0 $ y $ y= 1 $ luego $ a ^ {- 1} (yx)= 5 $ , y así $ m_ += 5 $ y $ - m_-= 2 $ . Así que el camino más corto se vuelve hacia atrás durante dos pasos: $ 0 \ a 4 \ a 1 $ .

Answer 2

Necesita encontrar enteros $ a $ y $ b $ tal que

$ 3A= 7b + 1 $

y de todos los valores (infinitamente muchos) de $ a $ usted quiere el que minimice $ | a | $ . En este caso, podemos ver por prueba y error que el conjunto de soluciones es $ a= 5 + 7n $ para valores enteros de $ n $ , y para minimizar $ | a | $ Tomamos $ n= -1 $ , para que $ A= -2 $ y la ruta más corta es $ 0 \ a 4 \ a 1 $ .

En general, habrá infinitamente muchas soluciones a $ pa= qb + 1 $ siempre y cuando $ p $ y $ q $ son co-prime (no compartir ningún factor común que no sea $ 1 $ ), y puede usar el algoritmo euclidiano para encontrar el valor positivo más pequeño de $ A $ . Si el valor positivo más pequeño de $ a $ es $ A_0 $ luego el valor de $ A $ que minimiza $ | a | $ es $ A_0 $ o $ A_0 - Q $ .

Answer 3

Podemos generalizar fácilmente este problema: dado un grupo Finito G, dos elementos G y H en G, y un subconjunto S de G, encuentre el camino más corto de G a H en el gráfico cuyos vértices son los elementos de G y cuyos bordes son los elementos de S o los inversores respectivos de los elementos de S, es decir, dos vértices X e Y están adyacentes si y solo si Y= XR para algunos R, es un elemento de S o es un elemento inverso de algún elemento de S. Tenga en cuenta que este gráfico tiene | G | vértices y | s || g | Los bordes en una implementación de computadora explícita o implícita. Un exclusivo algoritmo de búsqueda de primeras en este gráfico que comienza en el vértice G y terminando una vez que se alcanza el vértice H rendirá la ruta más corta entre g y h en el tiempo O (| g | + | s || g |)= o ( | S || g |) tiempo. Además, en realidad no tenemos que construir este gráfico; Esto se debe a que ya sabemos lo que son todos los bordes. Solo tenemos que hacer un bucle a través de los vecinos del elemento de grupo actual en cada iteración del algoritmo de búsqueda de la primera opción.

En su caso, para cualquier entero positivo N, tenemos S= {3 MOD N} y que el orden del grupo aditivo de las clases de residuos mod n es n, por lo que podemos encontrar la ruta más corta entre cualquiera de los dos residuos especificados Clases mod n en O (n)= o (n) tiempo.