Me puede dar una respuesta parcial a la primera pregunta:
Mientras que el problema general de la detección de
un camino Hamiltoniano o ciclo en un
sin cuadrícula gráfico es conocido por ser
NP-completo, hay interesantes
casos especiales donde eficiente
el polinomio de algoritmos en tiempo existen para
la enumeración de todos esos caminos/ciclos?
Si la cuadrícula gráfico es "sólido", es decir, no tiene agujeros, entonces existe un polinomio en tiempo del algoritmo por Umans y Lenhart (papel aquí) que va a encontrar un ciclo Hamiltoniano, o rechazar la gráfica si no hay ciclo existe. El algoritmo busca en primer lugar un máximo de coincidencia y, a continuación, se descompone el gráfico en "estática alternancia de bandas", que puede llevarse a cabo de manera eficiente. La producción del ciclo Hamiltoniano se logra cambiando la coincidencia dependiendo de cómo la estática de la alternancia de bandas están establecidos.
Si bien puede ser exponencialmente muchos diferentes de H ciclos, es posible enumerar con polinomio de retardo (es decir sólo tener que esperar un polinomio cantidad de tiempo antes de la salida de la siguiente) cambiando el orden en el que uno atraviesa la estática de la alternancia de bandas, y/o evolución de los subyacentes a juego. (Advertencia: el algoritmo de enumeración puede ser necesario más cuidado que mi handwaving, para asegurarse de que sólo exponencialmente-muchos de los duplicados de los ciclos se obtienen antes de que una nueva. Parece, sin embargo, que uno simplemente podría construir diferentes ciclos en paralelo y, a continuación, dar prioridad a aquellos que se apartan el uno del otro.)
Así agujero libre de la cuadrícula aparecen los gráficos para ser un caso especial.
