el

 

Gráfico de PIEZAS DE AJEDREZ

DOWNLOAD Mathematica NotebookDownload Wolfram NotebookDescargar Wolfram Notebook
KnightGraphChessboard

El gráfico de la pieza (caballo) es un gráfico de vértices en el que cada vértice representa un cuadrado en un tablero m×nde ajedrez.      chessboard, tablero de ajedrez, y cada borde corresponde a una jugada legal de un caballo (que sólo puede realizar movimientos que desplacen simultáneamente una casilla a lo largo de un eje y dos a lo largo del otro). Es por tanto un grafo de caballo es un grafo en vértices en el que cada vértice representa una casilla en un tablero de ajedrez, y cada borde corresponde a una jugada legal por un caballo (que sólo puede hacer movimientos que se desplacen simultáneamente una casilla a lo largo de un eje y dos a lo largo del otro). Por lo tanto, es un gráfico de salto.(1,2)-leaper graph.El grafo de caballero es un grafo en vértices en el que cada vértice representa una casilla en un tablero de ajedrez, y cada borde corresponde a una jugada legal por un caballo (que sólo puede hacer movimientos que se desplacen simultáneamente una casilla a lo largo de un eje y dos a lo largo del otro). Por lo tanto, es un gráfico de salto.

KnightsTourGraph

n×n knight graphs abstracted from the chessboard are illustrated above for n=3, ..., 6. The 1×1 knight graph is the singleton graph K_1 and the 2×2 knight graph is isomorphic to the empty graph K^__4 (since no square is reachable from any other by a knight).Grafos de caballo abstraídos de El tablero de ajedrez se ilustra arriba para , ..., 6. El caballo grafo es el soltero gráfico y el El grafo de caballo es isomorfo al grafo vacío (ya que ningún cuadrado es alcanzable desde ningún otro por un caballo).El gráfico del caballo consta de un ciclo de 8 junto con un vértice central aislado (inalcanzable desde todos los demás cuadrados).

The number of edges in the n×n knight graph is 4(n-2)(n-1) (8 times the triangular numbers), so for n=1, 2, ..., the first few values are 0, 0, 8, 24, 48, 80, 120, ... (OEIS A033996).El número de aristas en la gráfica de caballos es (8 veces el triangular)

números), por lo que para , 2, ..., los primeros valores son 0, 0, 8, 24, 48, 80, 120, ... (OEIS A033996).

Knight graphs are bipartite and therefore are perfect.Los grafos de Knight son bipartitos y, por lo tanto, son Perfecto.

The following table summarizes some named graph complements of knight graphs.En la tabla siguiente se resumen algunos complementos de grafos con nombre de grafos de caballos.

GG^_
(2,3)-knight graph-Grafo de caballero(2,3)-queen graph-Gráfico de la reina
(3,3)-knight graph-caballero gráfico(3,3)-queen graph-Gráfico de la reina

The m×n knight graph is implemented in the Wolfram Language as KnightTourGraph[m, n], and precomputed properties are available in using GraphData[{"Knight", {m, n}}].El grafo de caballero se implementa en Wolfram Language como KnightTourGraph[m, n], y las propiedades precalculadas están disponibles en el uso de GraphData["Knight", m, n].

Closed formulas for the numbers c_k of k-graph cycles of the n×n knight graph are given by c_k=0 for k odd andLas fórmulas cerradas para los números de los ciclos de -grafo de la grafa de caballo están dadas por para impares y

c_4

=

{0 for n<=3; 2(3n^2-18n+26) otherwise

(1)

(E. Weisstein, Nov. 16, 2014).(E. Weisstein, 16 de noviembre de 2014).

A knight's path is a sequence of moves by a knight such that each square of the board is visited exactly once. It is therefore a Hamiltonian path on the corresponding knight graph. Conrad et al. (1994) shows that a knight's path exists on an n×n board iff n>=5.El camino de un caballo es una secuencia de movimientos de un caballo de tal manera que cada casilla del tablero se visita exactamente una vez. Por lo tanto, es un hamiltoniano
en el grafo de caballero correspondiente. Conrad y cols. (1994) muestra que Un camino de caballo existe en un tablero IFF.

KnightsTours

Las figuras anteriores muestran los caminos de seis caballos en un tablero de ajedrez, todos menos los primeros de los cuales son reentrantes. La ruta final tiene la propiedad adicional que Es un cuadrado semimágico con fila y columna sumas de 260 y sumas diagonales principales de 348 y 168 (Steinhaus 1999, p. 30).

Si la posición final de dicho camino es el alejamiento de un caballo de la posición inicial del caballo, el camino se denomina reentrante o cerrado y corresponde a un hamiltoniano
Ciclo en el gráfico de caballero subyacente. Conrad y cols. (1994) muestra que Un tour de caballos existe en un tablero iff y es parejo.

Algoritmos de retroceso (en los que se permite que el caballo se mueva lo más lejos posible hasta que llegue a un callejón sin salida, momento en el que hace una copia de seguridad de un número de pasos y luego intenta una ruta diferente) se puede usar para Encuentra Tours de Caballeros, pero estos métodos pueden ser muy lentos. Warnsdorff (1823) propuso Un algoritmo que encuentra una ruta sin ningún retroceso mediante el cálculo de calificaciones para Pasos "sucesores" en cada posición. Aquí, los sucesores de una posición son Aquellas plazas que aún no han sido visitadas y a las que se puede llegar con un solo movimiento desde la posición dada. La calificación es más alta para el sucesor cuyo número de sucesores es lo menos. De esta forma, se visitan primero las plazas que tienden a estar aisladas y, por lo tanto, se evitó que se aislara (Roth). El tiempo necesario para este algoritmo crece más o menos linealmente con el número de casillas del tablero de ajedrez, pero desafortunadamente La implementación de computadoras muestra que este algoritmo se encuentra con callejones sin salida para los tableros de ajedrez Más grande que , a pesar de que funciona bien en placas más pequeñas (Roth).

KnightsTours5-8

Conrad et al. (1994) discovered another linear time algorithm and proved that it solves the Hamiltonian path problem for all n>=5. The Conrad et al. algorithm works by decomposition of the chessboard into smaller chessboards (not necessarily square) for which explicit solutions are known. This algorithm is rather complicated because it has to deal with many special cases, but has been implemented in the Wolfram Language by A. Roth. Example tours are illustrated above for n×n boards with n=5 to 8.Conrad y cols. (1994) descubrieron otro algoritmo de tiempo lineal y demostraron que resuelve el problema del camino hamiltoniano para todos. El estudio Conrad et al. El algoritmo funciona por descomposición del tablero de ajedrez en tableros de ajedrez más pequeños (no necesariamente cuadrados) para los que Las soluciones son conocidas. Este algoritmo es bastante complicado porque tiene que lidiar con con muchos casos especiales, pero se ha implementado en el Wolfram
Lenguaje de A. Roth. Ejemplos de recorridos se ilustran arriba para tableros con hasta 8.

Los números de giros de caballos cerrados (no dirigidos) (es decir, ciclos hamiltonianos) en un tablero de ajedrez para , 2, ... son 0, 0, 9862, 13267364410532, ... (OEIS A001230; Ball y Coxeter 1987; Wegener 2000, pág. 369; Elkies y Stanley 2003). No hay tours cerrados para tablas con impares. Kraitchik (1942, pp. 264-265) también señala que hay hay 1728 caminos totales en la plaza, 8 de los cuales son simétricos, y hay cinco Trayectorias doblemente simétricas en la plaza. El número de ciclos que cubren el El grafo de caballo para un tablero de ajedrez fue calculado por Wegener y Löbbing (1996) como. También calcularon el número de recorridos no dirigidos, obteniendo una respuesta incorrecta (que no es divisible por 4 como debe ser). El valor correcto de aparece en el libro posterior de Wegener (Wegener 2000), y también concuerda con los libros inéditos cálculos de B. D. McKay.

Los recorridos más largos del caballo "sin cruzar" en una tabla para , 4, ... son 2, 5, 10, 17, 24, 35, ... (OEIS A003192).

The following table extends and corrects some additional results given by Kraitchik (1942, pp. 264-265). Here, DHP means geometrically distinct Hamiltonian paths, DSHP means geometrically distinct symmetric paths, HP means total (directed) Hamiltonian paths, DHC means geometrically distinct Hamiltonian cycles, and HC means total (directed) Hamiltonian cycles.La siguiente tabla amplía y corrige algunos resultados adicionales dados por Kraitchik (1942, pp. 264-265). Aquí, DHP significa trayectorias hamiltonianas geométricamente distintas, DSHP significa trayectorias simétricas geométricamente distintas, HP significa trayectorias hamiltonianas totales (dirigidas), DHC significa ciclos hamiltonianos geométricamente distintos y HC significa ciclos hamiltonianos totales (dirigidos).

tamañoDHPDSHPHPDHCHC
SloaneA118067A158074
3×200000
3×300000
3×431600
3×50000
3×60000
3×714210400
3×810479200
3×914616112000
3×107736096832
3×112698582134400
3×121435011449628352
3×133229625772800
3×143072
3×1500
3×1630848

Sorprendentemente, el número de ciclos hamiltonianos en el grafo de Knight viene dado por la recurrencia lineal de orden 21 ecuación

a_n=6a_(n-1)+64a_(n-2)-200a_(n-3)-1000a_(n-4)+3016a_(n-5)+3488a_(n-6)-24256a_(n-7)+23776a_(n-8)+104168a_(n-9)-203408a_(n-10)-184704a_(n-11)+443392a_(n-12)+14336a_(n-13)-151296a_(n-14)+145920a_(n-15)-263424a_(n-16)+317440a_(n-17)+36864a_(n-18)-966656a_(n-19)+573440a_(n-20)+131072a_(n-21)
(2)

with corresponding closed-form generating functioncon la correspondiente función generadora de forma cerrada

G(z)=(P(z))/(Q(z))
(3)
=32z^5+352z^6+3072z^7+30848z^8+295456z^9+...,
(4)

Dónde

P(z)=32(2048z^(22)+5120z^(21)-22016z^(20)-3328z^(19)+2784z^(18)+13888z^(17)+15360z^(16)-13392z^(15)-8176z^(14)+9536z^(13)-4z^(12)-3179z^(11)+616z^10+505z^9-116z^8-34z^7+5z^6+z^5)
(5)
Q(z)=-131072z^(21)-573440z^(20)+966656z^(19)-36864z^(18)-317440z^(17)+263424z^(16)-145920z^(15)+151296z^(14)-14336z^(13)-443392z^(12)+184704z^(11)+203408z^(10)-104168z^9-23776z^8+24256z^7-3488z^6-3016z^5+1000z^4+200z^3-64z^2-6z+1.
(6)

This result was obtained independently by D. E. Knuth and N. D. Elkies in April 1994, both using the so-called transfer-matrix method (Stanley 1999, Ch. 4.7; Elkies and Stanley 2003).Este resultado fue obtenido independientemente por D. E. Knuth y N. D. Elkies en abril de 1994, ambos utilizando el llamado método de matriz de transferencia (Stanley 1999, Cap. 4.7; Elkies y Stanley 2003).

The numbers of possible (directed) closed tours on a 4×k board for k=3, 4, ... are 16, 0, 164, 1488, 12756, 62176, 379376, 2426224, ... (OEIS A123935; Kraitchik 1942, p. 263). Like the 3×(2n) case, this sequence is known to be given by a linear recurrence relation with constant coefficients, although it appears this recurrence has not yet been explicitly computed.El número de posibles recorridos cerrados (dirigidos) en un tablero para , 4, ... son 16, 0, 164, 1488, 12756, 62176, 379376, 2426224, ... (OEIS A123935; Kraitchik 1942, p. 263). Al igual que el caso, se sabe que esta secuencia está dada por una relación de recurrencia lineal con constante coeficientes, aunque parece que esta recurrencia aún no se ha calculado explícitamente.

The m×n knight graph is Hamilton-laceable iff m>=6, n>=6, and at least one of m, n is even (Dupuis and Wagon 2014).El grafo del caballero es encajable a lo Hamilton, , y al menos uno de , es parejo (Dupuis y Wagon 2014).

Véase también

Gráfico de antílope, gráfico de alfil, gráfico de obispo negro, camello
Gráfico, Ajedrez, Fiveleaper
Gráfico, Gráfico de jirafa, hamiltoniano
Ciclo, Camino hamiltoniano, Rey
Gráfico, Problema de Reyes, Caballos
Problema, Gráfico de Salto, Magia
Tour, Gráfico de la Reina, Reinas
Problema, Grafo de Torre, Tour, Panal triangular Acute Knight
Gráfico, panal triangular
Grafo de Caballo Obtuso, Grafo de Alfil Blanco, Gráfico de cebra

Comentarios

Publicar un comentario