En el campo matemático de la teoría de grafos, el problema de la ruta hamiltoniana y el problema del ciclo hamiltoniano son problemas para determinar si existe una ruta hamiltoniana (una ruta 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 dirigido o no dirigido ). Ambos problemas son NP-completos . [1]
El problema del ciclo hamiltoniano es un caso especial del problema del viajante , obtenido estableciendo la distancia entre dos ciudades en una si son adyacentes y dos en caso contrario, y verificando que la distancia total recorrida es igual an (si es así, la ruta es un circuito hamiltoniano; si no hay un circuito hamiltoniano, la ruta más corta será más larga).
Reducción entre el problema de la trayectoria y el problema del ciclo
Los problemas de encontrar un camino hamiltoniano y un ciclo hamiltoniano se pueden relacionar de la siguiente manera:
- En una dirección, el problema del camino hamiltoniano para el gráfico de G puede estar relacionado con el problema ciclo de Hamilton en un gráfico H obtenida de G mediante la adición de un nuevo vértice universal de x , la conexión de x para todos los vértices de G . Por lo tanto, encontrar un camino hamiltoniano no puede ser significativamente más lento (en el peor de los casos, en función del número de vértices) que encontrar un ciclo hamiltoniano.
- En la otra dirección, el problema ciclo de Hamilton para un gráfico G es equivalente al problema hamiltoniano camino en el gráfico H obtenida por adición de terminal ( grado -ona) vértices s y t unidos respectivamente a un vértice v de G y v', una copia dividida de v que da a v ' la misma vecindad que v . La trayectoria hamiltoniana en H que atraviesa los vértices svx -...- y-v'-t corresponde al ciclo hamiltoniano en G que atraviesa vx -...- y (-v) . [2]
Algoritmos
¡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 de 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 utilizar 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 cubre exactamente los vértices en S y termina en v . Para cada elección de S y v , existe una ruta para ( S , v ) si y solo si v tiene un vecino w tal que existe una ruta 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 cubiertas de los ciclos, que puede resolverse calculando ciertos determinantes matriciales. Usando este método, mostró cómo resolver el problema del ciclo hamiltoniano en gráficas arbitrarias 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 hasta el tiempo o (1.415 n ). [7]
Para gráficos de máximo grado tres, una búsqueda de seguimiento cuidadosa puede encontrar un ciclo hamiltoniano (si existe) en el tiempo O (1.251 n ). [8]
Las rutas y ciclos hamiltonianos se pueden encontrar utilizando un solucionador SAT .
Debido a la dificultad de resolver los problemas de ciclo y trayectoria hamiltonianos en computadoras convencionales, también se han estudiado en modelos informáticos no convencionales. Por ejemplo, Leonard Adleman demostró que el problema de la ruta hamiltoniana puede resolverse utilizando una computadora de ADN . Aprovechando el paralelismo inherente a las reacciones químicas, el problema puede resolverse utilizando varios 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]
También se ha propuesto una solución óptica al problema hamiltoniano. [10] La idea es crear una estructura en forma de gráfico hecha de cables ópticos y divisores de haz que son atravesados por la luz para construir una solución al problema. El punto débil de este enfoque es la cantidad de energía requerida, que es exponencial en el número de nodos.
Complejidad
El problema de encontrar un ciclo o camino hamiltoniano está en FNP ; el problema de decisión análogo es probar si existe un ciclo o camino hamiltoniano. Los problemas del ciclo hamiltoniano dirigido y no dirigido fueron dos de los 21 problemas NP-completos de Karp . Permanecen NP-completos incluso para tipos especiales de gráficos, como:
- gráficos bipartitos , [11]
- gráficos planos no dirigidos de máximo grado tres, [12]
- Gráficos planos dirigidos con grado y grado máximo como máximo dos, [13]
- planos no dirigidos sin puente 3- grafos bipartitos regulares ,
- Gráficos bipartitos regulares de 3 conectados, [14]
- subgrafos del gráfico de cuadrícula cuadrada , [15]
- subgrafos cúbicos del gráfico de cuadrícula cuadrada. [dieciséis]
Sin embargo, para algunas clases especiales de gráficos, el problema se puede resolver en tiempo polinomial:
- Los grafos planares de 4 conectados son siempre hamiltonianos por un resultado debido a Tutte , y la tarea computacional de encontrar un ciclo hamiltoniano en estos grafos se puede llevar a cabo en tiempo lineal [17] calculando un llamado camino de Tutte .
- Tutte demostró este resultado mostrando que cada gráfico plano de 2 conexiones contiene una ruta de Tutte. Las trayectorias de Tutte, a su vez, se pueden calcular en tiempo cuadrático incluso para gráficas planas de 2 conexiones, [18] que pueden usarse para encontrar ciclos hamiltonianos y ciclos largos en generalizaciones de gráficas planas.
Poniendo todas estas condiciones juntas, queda abierto si las gráficas planas bipartitas regulares 3-conectadas deben contener siempre un ciclo hamiltoniano, en cuyo caso el problema restringido a esas gráficas no podría ser NP-completo; ver la conjetura de Barnette .
En los gráficos en los que todos los vértices tienen un grado impar, un argumento relacionado con el lema del apretón de manos muestra que el número de ciclos hamiltonianos a través de cualquier borde fijo es siempre par, por lo que si se da un ciclo hamiltoniano, entonces también debe existir un segundo. [19] Sin embargo, encontrar este segundo ciclo no parece ser una tarea computacional fácil. Papadimitriou definió la clase de complejidad PPA para encapsular problemas como éste. [20]
Referencias
Medios relacionados con el problema de la ruta hamiltoniana en Wikimedia Commons
- ^ Michael R. Garey y David S. Johnson (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 978-0-7167-1045-5 A1.3: GT37–39, págs. 199–200.
- ^ Reducción del ciclo hamiltoniano al camino hamiltoniano
- ^ Martello, Silvano (1983), "Un algoritmo enumerativo para encontrar circuitos hamiltonianos en un gráfico dirigido", ACM Transactions on Mathematical Software , 9 (1): 131-138, doi : 10.1145 / 356022.356030
- ^ Rubin, Frank (1974), "Un procedimiento de búsqueda de rutas y circuitos de Hamilton", Journal of the ACM , 21 (4): 576–80, doi : 10.1145 / 321850.321854
- ^ Bellman, R. (1962), "Tratamiento de programación dinámica del problema del viajante de comercio", Journal of the ACM , 9 : 61–63, doi : 10.1145 / 321105.321111.
- ^ Held, M .; Karp, RM (1962), "Un enfoque de programación dinámica para los problemas de secuenciación" (PDF) , J. SIAM , 10 (1): 196–210, doi : 10.1137 / 0110015 , hdl : 10338.dmlcz / 103900.
- ^ Björklund, Andreas (2010), "Sumas determinantes para la hamiltonicidad no dirigida", Proc. 51º Simposio de IEEE sobre fundamentos de la informática (FOCS '10) , págs. 173–182, arXiv : 1008.0541 , doi : 10.1109 / FOCS.2010.24 , ISBN 978-1-4244-8525-3.
- ^ Iwama, Kazuo; Nakashima, Takuya (2007), "Un algoritmo exacto mejorado para TSP de grafos cúbicos", Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007) , Lecture Notes in Computer Science, 4598 , págs. 108-117, CiteSeerX 10.1.1.219.1672 , doi : 10.1007 / 978-3-540-73545-8_13 , ISBN 978-3-540-73544-1.
- ^ Adleman, Leonard (noviembre de 1994), "Cálculo molecular de soluciones a problemas combinatorios", Science , 266 (5187): 1021–1024, Bibcode : 1994Sci ... 266.1021A , CiteSeerX 10.1.1.54.2565 , doi : 10.1126 / science .7973651 , JSTOR 2885489 , PMID 7973651.
- ^ Mihai Oltean (2006). Un dispositivo basado en la luz para resolver el problema de la trayectoria hamiltoniana . Computación no convencional. Springer LNCS 4135. págs. 217–227. arXiv : 0708.1496 . doi : 10.1007 / 11839132_18 .
- ^ "Prueba de que la existencia de un Hamilton Path en un gráfico bipartito es NP-completo" . Intercambio de pilas de informática . Consultado el 18 de marzo de 2019 .
- ^ Garey, MR ; Johnson, DS ; Stockmeyer, L. (1974), "Algunos problemas NP-completos simplificados", Proc. Sexto Simposio ACM sobre Teoría de la Computación (STOC '74) , págs. 47–63, doi : 10.1145 / 800119.803884.
- ^ Plesńik, J. (1979), "La completitud NP del problema del ciclo hamiltoniano en dígrafos planos con límite de grado dos" (PDF) , Information Processing Letters , 8 (4): 199-201, doi : 10.1016 / 0020-0190 (79) 90023-1.
- ^ Akiyama, Takanori; Nishizeki, Takao ; Saito, Nobuji (1980-1981), "NP-completitud del problema del ciclo hamiltoniano para gráficos bipartitos", Journal of Information Processing , 3 (2): 73-76, MR 0596313.
- ^ Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme (1982), "Hamilton Paths in Grid Graphs", SIAM Journal on Computing , 4 (11): 676–686, CiteSeerX 10.1.1.383.1078 , doi : 10.1137 / 0211056.
- ^ Buro, Michael (2000), "Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs" (PDF) , Conferencia sobre Computadoras y Juegos , Lecture Notes in Computer Science, 2063 , pp. 250-261, CiteSeerX 10.1.1.40 .9731 , doi : 10.1007 / 3-540-45579-5_17 , ISBN 978-3-540-43080-3.
- ^ Chiba, Norishige; Nishizeki, Takao (1989), "El problema del ciclo hamiltoniano se puede resolver en tiempo lineal para gráficos planos de 4 conexiones", Journal of Algorithms , 10 (2): 187-211, doi : 10.1016 / 0196-6774 (89) 90012- 6
- ^ Schmid, Andreas; Schmidt, Jens M. (2018), "Computing Tutte Paths", Actas del 45º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP'18), por aparecer.
- ^ Thomason, AG (1978), "Ciclos hamiltonianos y gráficos con colores de bordes únicos", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) , Annals of Discrete Mathematics, 3 , págs. 259-268 , doi : 10.1016 / S0167-5060 (08) 70511-9 , ISBN 9780720408430, MR 0499124.
- ^ Papadimitriou, Christos H. (1994), "Sobre la complejidad del argumento de la paridad y otras pruebas ineficientes de existencia", Journal of Computer and System Sciences , 48 (3): 498–532, CiteSeerX 10.1.1.321.7008 , doi : 10.1016 / S0022-0000 (05) 80063-7 , MR 1279412.