모듈 형 산술에서 가장 짧은 경로

Question

7 개의 꼭지점을 가지고 있으며, 각각은 서로 다른 정수 모듈로 7에 해당합니다.가장자리는 x + 3 ∈ Y mod 7이면 두 개의 꼭지점 X와 Y 사이에 존재합니다. 예를 들어, 0에서 3 사이의 가장자리와 5에서 2 사이의 가장자리가 있습니다. 0에서 1 사이의 최단 경로의 길이는 무엇입니까??

답변을 얻는 방법은 일련사의 정의를 적용하는 것입니다.가장자리가 IFF $ 7 |x + 3 - y $ .따라서 하나의 순환 그래프를 얻은 다음 응답을 얻습니다. 2. 노드 0과 노드 1 사이에서 가장 짧은 경로를 얻을 수 있도록 그래프를 그리지 않고 모듈 형 산술로 재생할 수있는 방법이 있습니까?

Answer 1

$ n $ 정점을 가지고있는 더 일반적인 경우를 고려해보십시오. $ x, y를 연결하십시오. $ $ xy \ equiv a \ pmod {n} $ ( $ n= 7) $ 및 $ a= 3 $ ).

그래프는 분리 된 사이클의 조합입니다. $ n $ 은 프라임 (귀하의 경우와 같이)이며, 단일주기입니다. 따라서 $ x $ 에서 $ y $ 에 이르기를 원한다면 $ a $ (modulo $ n $ ), $ $ (modulo $ n $ ). $ m $ math-container "> $ a $ (여기서 $ m $ 은 아마도 음수입니다) 그런 다음 $ x + ma \ equiv y \ pmod {n} $ , 즉 $ ma \ equiv yx \ pmod {n} $ . 이제 $ (a, n)= 1 $ (예 : $ n $ )라고 가정하게하십시오. Prime 및 $ 1 \ LEQ A \ LEQ N-1 $ ). 그런 다음 $ m \ equiv a ^ {- 1} (y-x) \ pmod {n} $

위의 방정식을 해결 ( $ x \ not \ equiv y \ pmod {n} $ 가정), $ 1, \ ldots, n-1 $ 및 다른 $ 1, $ m _ _ + $ $-1, \ ldots, - (n-1) $ 범위의 M _- $ . 거리는 $ \ min (m _ +, - m _-) $

$ n= 7 $ 및 $ a= 3 $ . $ a ^ {- 1}= 5 $ 을 계산할 수 있습니다. $ x= 0 $ 및 $ y= 1 $ $ a ^ {- 1} (yx)= 5 $ 및 $ m_ += 5 $ 및 $-m_-= 2 $ . 따라서 가장 짧은 경로는 $ 0 \ 4 \ ~ 1 $ 를

Answer 2

$ a $ 및 $ b $ 을 찾아야합니다

$ 3a= 7b + 1 $

및 $ a $ 의 모든 (무한히 많은 사람들) 값에서 $ | a | $ . 이 경우, 솔루션 세트가 $ a= 5 + 7n $ 에 대한 $ n $ , $ n= -1 $ 이므로 $ a= -2 $ 이고 가장 짧은 경로는 $ 0 \ 4 \ ~ 1 $ .

일반적으로 $ PA= QB + 1 $ 에 대한 $ p $의 솔루션이 무한히 많은 솔루션이 있습니다. 및 $ q $ 은 co-prime ( $ 1 $ )와 $ a $ . $ a $ 의 가장 작은 양의 값이 $ a_0 $ 이고 $ | $ 을 최소화하는 수학 용기 "> $ a $ 은 $ a_0 $ 또는 $ A_0 - Q $

Answer 3

우리는이 문제를 쉽게 일반화 할 수 있습니다. 유한 그룹 G, 두 요소 G 및 H는 G의 S 서브 세트가 G의 요소가 G의 요소 인 그래프에서 G 로의 최단 경로를 찾습니다. 가장자리는 S 또는 S의 요소의 각 요소 인 것, 즉 2 개의 r의 요소 중 하나 인 y= xr에 대한 y= xr의 경우에만 두 개의 정점 X 및 y가 인접하고 있거나 일부 요소의 요소가있는 경우 S.이 그래프는 | g | 정점과 | S || G | 명시 적 또는 암시 적 컴퓨터 구현에서 가장자리. 정점 G에서 시작하여 정점 H에 도달하면이 그래프의 간단한 넓은 검색 알고리즘은 시간 o (| g | + | s || g | g |)= o (|)= h의 가장 짧은 경로를 산출합니다 ( | S || g |) 시간. 또한, 우리는 실제로이 그래프를 구성하지 않아도됩니다. 이것은 이미 모든 가장자리가 무엇인지 이미 알고 있기 때문입니다. 우리는 방금 최초로 검색 알고리즘의 모든 반복에서 현재 그룹 요소의 이웃을 통해 루프해야합니다.

귀하의 경우, 양의 정수 N에 대해, 우리는 S= {3 mod n}을 가지고 있으며, 잔류 물질 클래스 MOD n의 첨가제 그룹의 순서는 n 개의 지정된 잔류 물 사이의 최단 경로를 찾을 수 있기 때문입니다. o (n)= o (n) 시간의 클래스 mod n.