Percorso più breve in aritmetica modulare
Supponiamo di avere 7 vertici, ciascuno dei quali corrisponde a un diverso intero modulo sette. Il bordo esiste tra due vertici x e y se x + 3 ≡ y mod 7. Ad esempio, c'è un bordo tra 0 e 3 e un bordo tra 5 e 2. Qual è la lunghezza del percorso più breve tra 0 e 1 ?
Il mio metodo per ottenere la risposta è applicare la definizione di congruenza. Il bordo esce iff$7 | x + 3 - y$. Quindi, ho ottenuto un grafico ciclico e poi ho ottenuto la risposta è 2. Esiste un metodo con cui posso giocare con l'aritmetica modulare senza disegnare un grafico in modo da poter ottenere il percorso più breve tra il nodo 0 e il nodo 1?
Risposte
Consideriamo il caso più generale in cui hai $n$ vertici e ti connetti $x,y$ Se $x-y \equiv a \pmod{n}$ (nel tuo caso, $n = 7$ e $a = 3$).
Il tuo grafico è un'unione di cicli disgiunti. quando$n$è primo (come nel tuo caso), è un ciclo singolo. Quindi se vuoi arrivare da$x$ per $y$, o continui ad aggiungere $a$ (modulo $n$), di continuare a sottrarre $a$ (modulo $n$). Se aggiungi$m$ volte il valore $a$ (dove $m$ è forse negativo) allora $x+ma \equiv y \pmod{n}$, questo è, $ma \equiv y-x \pmod{n}$. Supponiamo ora che$(a,n) = 1$ (per esempio, $n$ è primo e $1 \leq a \leq n-1$). Poi$m \equiv a^{-1}(y-x) \pmod{n}$.
Risolvendo l'equazione precedente (assumendo $x \not\equiv y \pmod{n}$), ci sarà una soluzione $m_+$ nell'intervallo $1,\ldots,n-1$ e un altro $m_-$ nell'intervallo $-1,\ldots,-(n-1)$. La distanza è$\min(m_+,-m_-)$.
Nel tuo caso, $n = 7$ e $a = 3$. Possiamo calcolare$a^{-1} = 5$. Se$x = 0$ e $y = 1$ poi $a^{-1}(y-x) = 5$, e così $m_+ = 5$ e $-m_- = 2$. Quindi il percorso più breve va all'indietro per due passaggi:$0 \to 4 \to 1$.
Devi trovare numeri interi $a$ e $b$ tale che
$3a = 7b + 1$
e da tutti i (infinitamente molti) valori di $a$ vuoi quello che minimizza $|a|$. In questo caso, possiamo vedere per tentativi ed errori che l'insieme di soluzioni è$a=5+7n$ per valori interi di $n$e per ridurre al minimo $|a|$ prendiamo $n=-1$, così che $a=-2$e il percorso più breve è $0 \to 4 \to 1$.
In generale, ci saranno infinite soluzioni a $pa = qb + 1$ fintanto che $p$ e $q$ sono co-prime (non condividono fattori comuni diversi da $1$) e puoi usare l' algoritmo euclideo per trovare il valore positivo più piccolo di$a$. Se il valore positivo più piccolo di$a$ è $a_0$ quindi il valore di $a$ che minimizza $|a|$ è l'uno o l'altro $a_0$ o $a_0 - q$.
Possiamo facilmente generalizzare questo problema: dato un gruppo finito G, due elementi g e h in G e un sottoinsieme S di G, trova il cammino più breve da g ad h nel grafo i cui vertici sono gli elementi di G e i cui bordi sono gli elementi di S o le rispettive inverse degli elementi di S, cioè due vertici x e y sono adiacenti se e solo se y = xr per qualche r che è o un elemento di S o è un inverso di qualche elemento di S. Notare che questo grafico ha | G | vertici e | S || G | bordi in un'implementazione del computer esplicita o implicita. Un semplice algoritmo di ricerca in ampiezza su questo grafico che inizia dal vertice g e termina una volta raggiunto il vertice h produrrà il percorso più breve tra geh nel tempo O (| G | + | S || G |) = O ( | S || G |) tempo. Inoltre, non dobbiamo effettivamente costruire questo grafico; questo perché sappiamo già cosa sono tutti i bordi. Dobbiamo solo scorrere i vicini dell'elemento di gruppo corrente ad ogni iterazione dell'algoritmo di ricerca in ampiezza.
Nel tuo caso, per qualsiasi numero intero positivo n, abbiamo S = {3 mod n} e che l'ordine del gruppo additivo delle classi di residui mod n è n, quindi possiamo trovare il percorso più breve tra due classi di residui specificate mod n in O (n) = O (n) tempo.