El ciclo de los gráficos y la ruta de acceso gráficos son fácilmente relacionados, en la medida de como ganar vs perdiendo posiciones. En el momento de realizar la jugada inicial en un ciclo de $C_n$ gráfico, se convierte en equivalente para el jugador contrario a moverse en un camino de $P_{n+1}$ donde el primer y el último nodos ya están numeradas $0$ (y el $n-1$ entre nodos todavía están sin numerar).
De hecho, posteriormente, es más eficiente para representar el intermedio gráfica de juego de los estados como una "unión" de la ruta de subdiagramas cuyos sin numerar nodos son disjuntas. Es conveniente considerar artificialmente la adición de nodos numerados $-1$ a los extremos de lo contrario, sin numerar ruta de gráficos, lo que sin numerar cada nodo tiene exactamente dos vecinos, y esto no afecta a los resultados de los juegos.
Es decir, una trayectoria inicial de gráfico de $P_k$ es equivalente a un trazado gráfico de $P_{k+2}$ con la primera y la última nodos numerados $-1$. El siguiente paso sería el número uno de la $k$ sin numerar nodos, efectivamente dividiendo el juego del gráfico en dos caminos, cada uno con un cero en un extremo y un $-1$ en el otro, o se sale de un solo tramo $P_{k+1}$, con un cero en un extremo y un $-1$ en el otro.
De esta manera intermedio, el estado del juego, para un ciclo de $C_n$ o path $P_n$ puede ser representado como una colección ordenada de los "componentes" que la partición de las sin numerar nodos en los arreglos de forma compacta especificado por $p(a,b,k)$ donde $a \ge b$ son los números de los dos extremos de un camino que, de lo contrario se compone de $k \gt 0$ sin numerar nodos entre esos extremos.
Actualización:
El uso de estos más compacto de la "ruta" de los segmentos para representar a la "mesa" (parcialmente numeradas gráficos), simetrías/equivalencias pueden ser más reconocido de manera eficiente. Se ejecuta con quince sin numerar nodos ahora tomar varios minutos en vez de en la mayor parte de un día.
Un llamativo patrón emerge. La siguiente tabla muestra el ganar o perder estado de un solo segmento de la ruta path(A,C,K), habiendo K aún sin numerar nodos entre los extremos numeradas A y C respectivamente:
(A,C)\K = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |...even | odd |
=====================================================================
(-1,-1) : L : L : W : L : L : L : L : W : L :... W | L |
( 0,-1) : W : W : W : W : W : W : L : W : L :... W | L |
( 0, 0) : W : W : W : W : W : W : W : W : L :... W | L |
( 1,-1) : L : W : L : W : W : W : L : W : L :... W | L |
( 1, 0) : L : W : W : W : W : W : W : W : L :... W | L |
( 1, 1) : L : L : L : W : L : W : W : W : L :... W | L |
( 2,-1) : W : W : W : W : W : W : L : W : L :... W | L |
( 2, 0) : W : W : W : W : W : W : W : W : L :... W | L |
( 2, 1) : W : W : L : W : W : W : W : W : L :... W | L |
( 2, 2) : W : W : W : L : W : W : W : W : L :... W | L |
Mientras que las columnas de a $k=1,\ldots,7$ contienen una buena cantidad de variación, más caminos parecen ser exclusivamente de ganar por $k$ aun y perdiendo por $k$ impar, independientemente de los extremos. Los cálculos se han hecho para todos los extremos que se muestra a $k=15$, y "por defecto" extremos $a=c=-1$$k=16,17$.
Algunos resultados generales
Intuitivamente debe haber algún tipo de Nim-como regla para determinar el ganar o perder la condición de estas colecciones de rutas numeradas extremos. Hasta ahora sólo he sido capaz de demostrar las siguientes fácil lema.
Supongamos que el estado del juego, $S$ se puede expresar como la unión de dos subdiagramas $S_1$ $S_2$ son tales que no sin numerar nodo es compartida por $S_1$$S_2$. Si $S_1$ $S_2$ están perdiendo posiciones (es decir, para el jugador requerido para mover el siguiente), y si tanto $S_1$ $S_2$ incluso han condes de sin numerar nodos, $S$ es una posición perdedora (y también tiene un recuento de las sin numerar nodos, aka se mueve a la izquierda).
La prueba es fácil. Como el actual jugador se mueve en $S_1$ o $S_2$, el oponente responde con una perfecta defensa de moverse en consecuencia. La actualización del estado del juego, es de nuevo una unión de dos posiciones perdedoras, con un número par de movimientos de izquierda en cada uno, salvo un par de jugadas "acabados" $S_1$ o $S_2$, dejando solo la inacabada subgrafo con su posición perdedora.
Un corolario inmediato de esto es que si $S_1$ es una posición ganadora con un número impar de movimientos de izquierda, y $S_2$ (disjunta de a $S_1$ a sin numerar nodos) es una posición perdedora con un número par de movimientos de la izquierda, luego a la "unión" de $S_1$ $S_2$ es una posición ganadora. La prueba es sólo para observar que, después de hacer una jugada ganadora en $S_1$, uno se queda con una mala posición (ya sea por el lema anterior, o por agotar $S_1$, dejando sólo a $S_2$).
