matemáticas: verifique si una configuración es posible: demuestre que hay una ruta hamiltoniana en un subconjunto conectado del gráfico de cuadrícula cuadrada

Lo que parece estar preguntando (suponiendo que los cuadrados estén completamente llenos), es encontrar un camino hamiltoniano en un subconjunto conexo del gráfico de cuadrícula cuadrada.

Definiciones (tomadas de Wikipedia)

A camino hamiltoniano (o ruta rastreable) es una ruta en un gráfico dirigido o no dirigido que visita cada vértice exactamente una vez.

A gráfico de cuadrícula cuadrada es el gráfico cuyos vértices corresponden a los puntos en el plano con coordenadas enteras, las coordenadas x están en el rango 1,…, n, las coordenadas y están en el rango 1,…, m, y dos vértices son conectados por una arista siempre que los puntos correspondientes estén a distancia 1.

Por lo que puedo decir, la respuesta es que el Problema del camino hamiltoniano es un problema NP-completo, lo que significa que no existe un algoritmo de tiempo polinomial para determinar si un gráfico arbitrario contiene una ruta hamiltoniana. En otras palabras, dada una forma lo suficientemente grande, podría llevar casi una eternidad descubrir si existe una solución para el problema planteado.


Una simple heurística puede determinar si no hay solución: si un cuadrado está conectado solo con otro cuadrado (es decir, tiene un grado de 1), debe ser el primero o el último cuadrado visitado, ya que no se puede retroceder. Por lo tanto, cualquier forma con más de 2 cuadrados (marcados con «1» en la imagen de abajo) no tiene solución.

Sin embargo, lo contrario no es cierto. La forma de abajo a la derecha tiene 2 cuadrados con grado 1, pero tampoco se puede resolver.

grados de vértice agregados


Otra heurística (cortesía de Lopsy): colorea los cuadrados como un tablero de ajedrez. El número de cuadrados blancos y negros solo puede diferir en 1 si es solucionable. Si, por ejemplo, hay un cuadrado blanco más que negro, entonces el camino debe comenzar y terminar en blanco.

En este caso, la forma de T satisface la heurística mientras que la forma de la derecha no. Ambos no son solucionables, lo que nuevamente muestra que lo contrario es falso.

tablero de damas


También puede simplificar formas eliminando un vértice de grado 1 si y solo si está conectado a un vértice de grado 2. Por ejemplo, las siguientes formas son equivalentes en términos de su capacidad de resolución:

formas T equivalentes


Pongamos en práctica lo que hemos aprendido. Aquí hay una forma compleja que satisface ambas heurísticas (solo 1 vértice de grado 1, y hay 7 cuadrados negros frente a 6 cuadrados claros). Pero podemos quitar el vértice de grado 1 porque está conectado a un vértice de grado 2, y ahora la nueva forma ya no satisface la heurística del tablero de ajedrez. Entonces, la forma no tiene un camino hamiltoniano.

Forma compleja


Esta es realmente una pregunta más para matemáticas o informática:
https://cstheory.stackexchange.com/questions/tagged/hamiltonian-paths
https://mathoverflow.net/questions/tagged/hamiltonian-paths

Esto también puede ser de interés (algoritmos para encontrar caminos hamiltonianos para gráficos en forma de L, C, F y E en una cuadrícula): http://www.hindawi.com/journals/jam/2012/475087/

Deja un comentario