En el campo matemático de la teoría de grafos, el problema del camino hamiltoniano y el problema del ciclo hamiltoniano son problemas para determinar si existe un camino hamiltoniano (un camino en un gráfico dirigido o no dirigido que visita cada vértice exactamente una vez) o un ciclo hamiltoniano en un gráfico dado ( ya sea dirigida o no dirigida ). Ambos problemas son NP-completos . [1]
El problema del ciclo hamiltoniano es un caso especial del problema del viajante de comercio , que se obtiene fijando la distancia entre dos ciudades en una si son adyacentes y dos en caso contrario, y comprobando que la distancia total recorrida es igual a n (si es así, la ruta es un circuito hamiltoniano; si no hay un circuito hamiltoniano, la ruta más corta será más larga).
¡ Hay n ! diferentes secuencias de vértices que podrían ser caminos hamiltonianos en un gráfico de n vértices dado (y lo son, en un gráfico completo ), por lo que un algoritmo de búsqueda de fuerza bruta que pruebe todas las secuencias posibles sería muy lento. Uno de los primeros algoritmos exactos para encontrar un ciclo hamiltoniano en un gráfico dirigido fue el algoritmo enumerativo de Martello. [3] Un procedimiento de búsqueda por Frank Rubin [4]divide los bordes del gráfico en tres clases: los que deben estar en la ruta, los que no pueden estar en la ruta y los indecisos. A medida que avanza la búsqueda, un conjunto de reglas de decisión clasifica los bordes indecisos y determina si detener o continuar la búsqueda. El algoritmo divide el gráfico en componentes que se pueden resolver por separado. Además, se puede usar un algoritmo de programación dinámica de Bellman, Held y Karp para resolver el problema en el tiempo O( n 2 2 n ). En este método, se determina, para cada conjunto S de vértices y cada vértice v en S , si hay un camino que cubra exactamente los vértices en S y termine env . Para cada elección de S y v , existe un camino para ( S , v ) si y solo si v tiene un vecino w tal que existe un camino para ( S − v , w ), que se puede buscar a partir de información ya calculada en el programa dinámico. [5] [6]
Andreas Björklund proporcionó un enfoque alternativo utilizando el principio de inclusión-exclusión para reducir el problema de contar el número de ciclos hamiltonianos a un problema de conteo más simple, de contar las coberturas de los ciclos, que se puede resolver calculando ciertos determinantes matriciales. Usando este método, mostró cómo resolver el problema del ciclo hamiltoniano en gráficos arbitrarios de n -vértices mediante un algoritmo de Monte Carlo en el tiempo O (1.657 n ); para gráficos bipartitos, este algoritmo se puede mejorar aún más al tiempo o (1.415 n ). [7]
Para gráficos de máximo grado tres, una búsqueda cuidadosa de retroceso puede encontrar un ciclo hamiltoniano (si existe) en el tiempo O (1.251 n ). [8]
Debido a la dificultad de resolver los problemas de ruta y ciclo hamiltonianos en computadoras convencionales, también se han estudiado en modelos no convencionales de computación. Por ejemplo, Leonard Adleman demostró que el problema de la ruta hamiltoniana puede resolverse usando una computadora de ADN . Explotando el paralelismo inherente a las reacciones químicas, el problema puede resolverse utilizando una serie de pasos de reacción química lineales en el número de vértices del gráfico; sin embargo, requiere un número factorial de moléculas de ADN para participar en la reacción. [9]