Problema del camino Hamiltoniano

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda

En el campo matemático de la teoría de grafos, el problema del camino hamiltoniano y el problema ciclo de Hamilton son problemas de determinar si un camino hamiltoniano o un ciclo de Hamilton existe en un grafo dado (ya sea dirigido o no dirigido). Ambos problemas son NP-completo.[1]

Relación entre problemas[editar]

Existe una relación simple entre los problemas de encontrar un camino de Hamilton y un ciclo Hamiltoniano. En una dirección, el problema del camino Hamiltoniano para el grafo G es equivalente al problema ciclo Hamiltoniano en un grafo H obtenido de G mediante la adición de un nuevo vértice y de la conexión a todos los vértices de G. Por lo tanto, la búsqueda de un camino de Hamilton no puede ser significativamente más lenta (n el peor de los casos, como una función del número de vértices) que encontrar un ciclo de Hamilton.

En la otra dirección, un grafo G tiene un ciclo de Hamilton utilizando la arista uv y sólo si el grafo H es obtenido por G mediante la sustitución de la arista por un par de vértices de grado 1, uno conectado a u y el otro conectado a v, tiene un camino de Hamilton. Por lo tanto, al tratar esta sustitución para todas las aristas incidentes hasta cierto vértice seleccionado de G, el problema del ciclo Hamiltoniano puede ser resuelto como máximo por n cálculos en la mayoría de los caminos Hamiltonianos, donde n es el número de vértices en el grafo.

El problema del Ciclo hamiltoniano es también un caso especial del Problema del viajante, obtenido mediante el establecimiento de la distancia entre dos ciudades a uno si son adyacentes y dos en otro caso, y la verificación de que la distancia total recorrida es igual a n (si es así, la ruta es un circuito hamiltoniano; si no hay circuito Hamiltoniano a continuación entonces la ruta más corta será más larga).

Algoritmos[editar]

Hay n! diferentes secuencias de vértices que pueden ser caminos Hamiltonianos dado un grafo de n vértices (y son, en un grafo completo), por lo que un algoritmo de búsqueda de fuerza bruta que pone a prueba todas las posibles secuencias serían muy lento. Hay varios enfoques más rápidos. Un procedimiento de búsqueda por Frank Rubin[2]​ divide a las aristas del grafo en tres clases: los que deben estar en el camino, los que no pueden estar en el camino, e indecisos. A medida que procede la búsqueda, un conjunto de reglas de decisión que clasifica las aristas indecisas, y determina si se debe detener o continuar la búsqueda. El algoritmo divide el grafo en componentes que pueden ser resueltas por separadas. Además, un algoritmo de programación dinámica de Bellman, Held, y Karp puede ser utilizado para resolver el problema en un tiempo O(n2 2n). En este método, se determina, para cada conjunto S de vértices y cada vértice v en S, si existe un camino que cubre exactamente los vértices en S y termina en v. Para cada elección de S y v, existe un camino para (S,v) si y sólo si v tiene un vecino w tal que existe un camino para (S − v,w), que puede ser visto de la información ya calculada en la solución dinámica.[3][4]

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 del ciclo, que puede ser resuelto mediante el cálculo de ciertos determinantes. El uso de este método, se mostró cómo resolver el problema del ciclo Hamiltoniano en los grafos n-vértices arbitrarios mediante un Algoritmo de Monte Carlo en orden O(1.657n); para grafos bipartitos este algoritmo puede ser mejorado en orden O(1.414n).[5]

Para grafos de máximo grado tres, una búsqueda cuidadosa puede dar marcha atrás y encontrar un ciclo de Hamilton (si existe) en orden O(1.251n).[6]

Debido a la dificultad de resolver el camino de Hamilton y problemas del ciclo en los equipos convencionales, también se han estudiado en modelos poco convencional de la computación. Por ejemplo, Leonard Adleman mostró que el problema del camino Hamiltoniano puede ser resuelto usando un ordenador ADN. Explotar el paralelismo inherente en las reacciones químicas, el problema puede ser resuelto utilizando un número de etapas de reacción químicas lineales en el número de vértices delgrafo, sin embargo, se requiere un número factorial de distintos tipos de molécula de ADN de participar en la reacción.[7]

Complejidad[editar]

El problema de encontrar un ciclo de Hamilton o el camino se encuentra en FNP; el problema de decisión análogo es para probar si existe un ciclo de Hamilton o el camino. Los problemas del ciclo Hamiltonianos dirigidos y no dirigidos, fueron dos de 21 problemas NP-completos de Karp. Permanecen NP-completo incluso para grafos planares no dirigidos de grado máximo tres,[8]​ para grafos planares dirigidos con grado de entrada y grado de salida como máximo dos,[9]​ para grafos bipartitos,3-regulares planares no dirigidos sin puente, 3-conexo grafos bipartitos 3-regulares.[10]​ Sin embargo, poner todas estas condiciones en conjunto, que permanece abiertas si grafos planares bipartitos 3-3-regulares conexos siempre debe contener un ciclo de Hamilton, en cuyo caso el problema restringido a estos grafos no podría ser NP-completos; véase la conjetura de Barnette.

En los grafos en los cuales todos los vértices tienen grado impar, un argumento relacionado con el lema del apretón de manos handshaking lemma muestra que el número de ciclos hamiltonianos a través de cualquier arista fijada, siempre es par, por lo tanto, en caso de que exista un ciclo de Hamilton, también debe existir un segundo ciclo.[11]​ Sin embargo, la búsqueda de este segundo ciclo no parece ser una tarea computacional sencilla. Papadimitriou definió la clase de complejidad PPA para encapsular problemas semejantes a este.[12]

Referencias[editar]

  1. Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5  A1.3: GT37–39, pp. 199–200.
  2. Rubin, Frank (1974), «A Search Procedure for Hamilton Paths and Circuits», Journal of the ACM 21 (4): 576-80, doi:10.1145/321850.321854 .
  3. Bellman, R. (1962), «Dynamic programming treatment of the travelling salesman problem», Journal of the ACM 9: 61-63, doi:10.1145/321105.321111 .
  4. Held, M.; Karp, R. M. (1962), «A dynamic programming approach to sequencing problems», J. Siam 10 (1): 196-210, doi:10.1137/0110015 .
  5. Björklund, Andreas (2010), «Determinant sums for undirected Hamiltonicity», Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10), pp. 173-182, ISBN 978-1-4244-8525-3, arXiv:1008.0541, doi:10.1109/FOCS.2010.24 .
  6. Iwama, Kazuo; Nakashima, Takuya (2007), «An improved exact algorithm for cubic graph TSP», Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007), Lecture Notes in Computer Science 4598, pp. 108-117, ISBN 978-3-540-73544-1, doi:10.1007/978-3-540-73545-8_13 .
  7. Adleman, Leonard (November), «Molecular computation of solutions to combinatorial problems», Science 266 (5187): 1021-1024, JSTOR 2885489, PMID 7973651, doi:10.1126/science.7973651 .
  8. Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), «Some simplified NP-complete problems», Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47-63, doi:10.1145/800119.803884 .
  9. Plesńik, J. (1979), «The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two», Information Processing Letters 8 (4): 199-201, doi:10.1016/0020-0190(79)90023-1 .
  10. Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980––1981), «NP-completeness of the Hamiltonian cycle problem for bipartite graphs», Journal of Information Processing 3 (2): 73-76, MR 596313  (enlace roto disponible en Internet Archive; véase el historial y la última versión)..
  11. Thomason, A. G. (1978), «Hamiltonian cycles and uniquely edge colourable graphs», Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics 3, pp. 259-268, ISBN 9780720408430, MR 499124, doi:10.1016/S0167-5060(08)70511-9 .
  12. Papadimitriou, Christos H. (1994), «On the complexity of the parity argument and other inefficient proofs of existence», Journal of Computer and System Sciences 48 (3): 498-532, MR 1279412, doi:10.1016/S0022-0000(05)80063-7 .