Quiero demostrar que no es cerrado caballero tour en un $3\ \times\ 8$ - tablero mediante la eliminación de $s$ vértices de la correspondiente caballero gráfico para obtener un gráfico con más de $s$ conectado componentes (lo que demostraría que no es hamiltoniano), pero no lo he conseguido hasta ahora.
¿Quién puede ayudar ?
Usted no tiene que demostrar de esa manera? No es difícil demostrar directamente que no existe cerrado caballeros tour de 3 x 8 junta. Empezar con plazas que tienen sólo dos movimientos disponibles, así que usted sabe tanto los movimientos deben ser parte de cualquier viaje.
La etiqueta de las plazas $$\begin{array}{cccccccc}1 & 4 & 7 & 10 & 13 & 16 & 19 & 22\\ 2 & 5 & 8 & 11 & 14 & 17 & 20 & 23\\ 3 & 6 & 9 & 12 & 15 & 18 & 21 & 24\end{array}$$ sólo Hay dos movimientos de 1, por lo que la ruta debe incluir 8 1 6. Del mismo modo, existen sólo dos de 3, por lo que debe incluir 8 3 4, y por lo tanto 4 3 8 1 6. Del mismo modo, existen sólo dos de 2, por lo que debe incluir 7 2 9. Si la ruta incluye 4 9 y 6 7, entonces tenemos el camino cerrado 4 3 8 1 6 7 2 9 4. La contradicción, por lo que se puede incluir en la mayoría de los una de las 4 9 y 6 7. Del mismo modo, se puede incluir en la mayoría de los una de las 4 11 y 6 11. Pero debe incluir una de las 4 9 y 4, 11 y uno de 6 7 y 6 11. Así wlog incluye 6 11 y 4 9. Así tenemos 11 6 1 8 3 4 9 2 7.
Exactamente el mismo argumento que en la mano derecha la mitad de la junta muestra que 14 no puede ser conectado tanto a 19 y 21. No puede ser conectado a 9 debido a que ya está conectado a 2 y 4, por lo que debe estar conectado a 7.
De nuevo por el mismo argumento en la mano derecha la mitad, de 17 años está conectado a 22 y 24. Por lo tanto el único cuadrados que puede ser conectado a 10 son de 5 y 15. Obviamente 5 también debe estar conectado a 12. 12 también debe estar conectado a 13 (7 y 17 años no están disponibles). Pero el 20 debe estar conectado a 13 y 15, así que tenemos el bucle cerrado 20, 13, 12, 5, 10, 15, 20. Contradicción.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
