Sí, ese grafo dirigido existe, con un camino "rápidamente" computable de longitud $O(\log|n-m|)$ de $m$ a $n$ para cualquier número entero distinto $m,n$ .
Primero construiré un dígrafo con esta propiedad pero en el que cada vértice tiene como máximo un grado de salida $8$ y luego mostrar cómo obtener a partir de él un dígrafo de grado exterior $2$ .
Denote por $v(x)$ el $2$ -valoracion adica del entero $x$ que es el único entero $e \geq 0$ tal que $x/2^e$ es un número entero impar; convencionalmente $v(0) = \infty$ .
Las aristas del gráfico que emanan de $x$ serán los siguientes. Si $x$ tiene valoración $e>0$ entonces $$ x \rightarrow x \pm 1, \phantom+ x \pm 2^{e-1}, \phantom+ x \pm 2^e, \phantom+ x \pm 3\cdot 2^e. $$ Si $x$ es impar, omitir $x \pm 2^{e-1}$ así que $x$ va sólo a $x \pm 1$ y $x\pm 3$ . Si $x=0$ entonces $x\mapsto \pm 1$ sólo.
Entonces:
(i) Para cada $e \geq 0$ los enteros de valoración $e$ constituyen una progresión aritmética de diferencia común $2^{e+1}$ . Podemos obtener de tales $x$ a $x \pm 2^{e+1}$ en dos pasos: si $e=0$ a continuación, sumar o restar $1$ dos veces; si $e>0$ a continuación, sumar o restar $2^{e-1}$ y luego $3 \cdot 2^{e-1}$ .
(ii) Si $v(x) = e$ y $|n-m| \leq 2^e$ podemos obtener de $m$ a $n$ en un máximo de $2 \phantom. \log_2 |n-m| + 1$ pasos. En efecto, si $|n-m| = 2^e$ basta con un paso, así que supongamos $|n-m| < 2^e$ y luego $|n-m| \in [2^d, 2^{d+1})$ con $d < e$ . Por simetría podemos suponer $n>m$ . Entonces $$ m \rightarrow m + 1 \rightarrow m + 2 \rightarrow m+4 \rightarrow \cdots \rightarrow m+2^d $$ en $d+1$ pasos, y luego en otro $d - v(n)$ pasos que alcanzamos $n$ escribiendo $$ n = m + 2^d + 2^{d-1} \pm 2^{d-2} \pm 2^{d-3} \pm \cdots \pm 2^{d-v(n)}. $$
(iii) Si $v(m) = e < f$ y $n$ es el número entero de valoración exactamente $f$ que está más cerca de $m$ entonces podemos obtener de $m$ a $n$ sur $f-e$ pasos. En el $i$ -ésima etapa, añada $\pm 2^{e+i-1}$ o $\pm 3 \cdot 2^{e+i-1}$ para alcanzar un número de valoración exactamente $e+i$ ; hay dos opciones, así que coge la que esté más cerca de $n$ . La distancia a $n$ siempre queda por debajo de $2^f$ por lo que en el paso $f-e$ golpeamos $n$ .
(iv) Por último, supongamos $m$ es impar y $|n-m| \in [2^k, 2^{k+1})$ . Visite $n'$ de valoración $k$ tal que $|n-n'| \leq 2^k$ . Así $|m-n'| < 3 \cdot 2^k$ . Por (iii), en $k$ pasos que obtenemos de $m$ a algunos $n_1$ tal que $|m-n_1| < 2^k$ y $v(n_1) = k$ . Así que $n_1=n'$ o $n_1 = n' \pm 2^{k+1}$ y en este último caso llegamos a $n'$ en otros dos pasos utilizando (i). Entonces, en un máximo de $2k+1$ más pasos alcanzamos $n$ utilizando (ii).
Hemos terminado, en un total de $3 \phantom. \log_2 |n-m| + O(1)$ pasos, porque si $m$ no es impar entonces podemos utilizar nuestro primer paso para pasar al número impar $m \pm 1$ más cerca de $n$ .
Ahora para pasar de grado $8$ hasta $2$ para cada $x \in {\bf Z}$ elija $f_i(x)$ para $i=0,1,2,\ldots,7$ para que $\{f_0(x),f_1(x),f_2(x),\ldots,f_7(x)\}$ es el conjunto de enteros alcanzables desde $x$ (con repeticiones si $x$ es impar o cero). Definir un nuevo gráfico de grado de salida $2$ como sigue: escriba cada número entero como $8x+i$ para algunos $x \in \bf Z$ y $i\in\{0,1,2,\ldots,7\}$ y luego $8x+i \rightarrow 8f_i(x)$ y $8x+i \rightarrow 8x+i'$ donde $i'=0$ si $i=7$ y $i'=i+1$ de lo contrario. Es decir, dividimos $\bf Z$ dirigida $8$ -lo que consume sólo una arista saliente por entero y nos deja con $8$ más aristas por ciclo para asignarlas como queramos, lo que nos permite utilizar nuestro gráfico de grados de salida $8$ . Cada paso de nuestro algoritmo se expande entonces a lo sumo a $8$ porque puede que tengamos que tomar hasta $7$ pasos dando vueltas hasta llegar al $i$ para dar el siguiente paso en nuestro gráfico original, y al final puede que aún tengamos que gastar un $7$ pasos para alcanzar el objetivo $n$ dentro de su ciclo. Pero eso sigue siendo como mucho $24 \phantom. \log_2 |n-m| + O(1)$ pasos, y aún con un algoritmo explícito y "rápido".
[ EDITAR podemos reducir $3 \phantom. \log_2 |n-m| + O(1)$ a $\frac52 \log_2 |n-m| + O(1)$ comprimiendo $$m \rightarrow m + 1 \rightarrow m + 2 \rightarrow m+4 \rightarrow \cdots \rightarrow m+2^d$$ a $$m \rightarrow m + 1 \rightarrow m + 4 \rightarrow m+16 \rightarrow \cdots \rightarrow m+2^d,$$ y probablemente haya otro múltiplo de $\log_2|n-m|$ que se guardará permutando $f_0(x),f_1(x),f_2(x),\ldots,f_7(x)$ para reducir el número de pasos que hay que dar dentro de $8$ -ciclos.]