fbpx
Wikipedia

Problema del camino Hamiltoniano

Abril 13, 2022

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

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 (en 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 solo 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

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 solo 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

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

  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, la primera versión y la última)..
  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 ..


  •   Datos: Q987652
  •   Multimedia: Hamiltonian path problem

Abril 13, 2022
problema, camino, hamiltoniano, campo, matemático, teoría, grafos, problema, camino, hamiltoniano, problema, ciclo, hamilton, problemas, determinar, camino, hamiltoniano, ciclo, hamilton, existe, grafo, dado, dirigido, dirigido, ambos, problemas, completo, Índ. En el campo matematico de la teoria 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 Indice 1 Relacion entre problemas 2 Algoritmos 3 Complejidad 4 ReferenciasRelacion entre problemas EditarExiste una relacion simple entre los problemas de encontrar un camino de Hamilton y un ciclo Hamiltoniano En una direccion el problema del camino Hamiltoniano para el grafo G es equivalente al problema ciclo Hamiltoniano en un grafo H obtenido de G mediante la adicion de un nuevo vertice y de la conexion a todos los vertices de G Por lo tanto la busqueda de un camino de Hamilton no puede ser significativamente mas lenta en el peor de los casos como una funcion del numero de vertices que encontrar un ciclo de Hamilton En la otra direccion un grafo G tiene un ciclo de Hamilton utilizando la arista uv y solo si el grafo H es obtenido por G mediante la sustitucion de la arista por un par de vertices de grado 1 uno conectado a u y el otro conectado a v tiene un camino de Hamilton Por lo tanto al tratar esta sustitucion para todas las aristas incidentes hasta cierto vertice seleccionado de G el problema del ciclo Hamiltoniano puede ser resuelto como maximo por n calculos en la mayoria de los caminos Hamiltonianos donde n es el numero de vertices en el grafo El problema del Ciclo hamiltoniano es tambien 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 verificacion de que la distancia total recorrida es igual a n si es asi la ruta es un circuito hamiltoniano si no hay circuito Hamiltoniano a continuacion entonces la ruta mas corta sera mas larga Algoritmos EditarHay n diferentes secuencias de vertices que pueden ser caminos Hamiltonianos dado un grafo de n vertices y son en un grafo completo por lo que un algoritmo de busqueda de fuerza bruta que pone a prueba todas las posibles secuencias serian muy lento Hay varios enfoques mas rapidos Un procedimiento de busqueda 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 busqueda un conjunto de reglas de decision que clasifica las aristas indecisas y determina si se debe detener o continuar la busqueda El algoritmo divide el grafo en componentes que pueden ser resueltas por separadas Ademas un algoritmo de programacion dinamica de Bellman Held y Karp puede ser utilizado para resolver el problema en un tiempo O n2 2n En este metodo se determina para cada conjunto S de vertices y cada vertice v en S si existe un camino que cubre exactamente los vertices en S y termina en v Para cada eleccion 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 puede ser visto de la informacion ya calculada en la solucion dinamica 3 4 Andreas Bjorklund proporciono un enfoque alternativo utilizando el principio de inclusion exclusion para reducir el problema de contar el numero de ciclos Hamiltonianos a un problema de conteo mas simple de contar las cubiertas del ciclo que puede ser resuelto mediante el calculo de ciertos determinantes El uso de este metodo se mostro como resolver el problema del ciclo Hamiltoniano en los grafos n vertices 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 maximo grado tres una busqueda cuidadosa puede dar marcha atras 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 tambien se han estudiado en modelos poco convencional de la computacion Por ejemplo Leonard Adleman mostro que el problema del camino Hamiltoniano puede ser resuelto usando un ordenador ADN Explotar el paralelismo inherente en las reacciones quimicas el problema puede ser resuelto utilizando un numero de etapas de reaccion quimicas lineales en el numero de vertices delgrafo sin embargo se requiere un numero factorial de distintos tipos de molecula de ADN de participar en la reaccion 7 Complejidad EditarEl problema de encontrar un ciclo de Hamilton o el camino se encuentra en FNP el problema de decision analogo 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 maximo tres 8 para grafos planares dirigidos con grado de entrada y grado de salida como maximo 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 podria ser NP completos vease la conjetura de Barnette En los grafos en los cuales todos los vertices tienen grado impar un argumento relacionado con el lema del apreton de manos handshaking lemma muestra que el numero de ciclos hamiltonianos a traves de cualquier arista fijada siempre es par por lo tanto en caso de que exista un ciclo de Hamilton tambien debe existir un segundo ciclo 11 Sin embargo la busqueda de este segundo ciclo no parece ser una tarea computacional sencilla Papadimitriou definio la clase de complejidad PPA para encapsular problemas semejantes a este 12 Referencias Editar 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 Rubin Frank 1974 A Search Procedure for Hamilton Paths and Circuits Journal of the ACM 21 4 576 80 doi 10 1145 321850 321854 Bellman R 1962 Dynamic programming treatment of the travelling salesman problem Journal of the ACM 9 61 63 doi 10 1145 321105 321111 Held M Karp R M 1962 A dynamic programming approach to sequencing problems J Siam 10 1 196 210 doi 10 1137 0110015 Bjorklund 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 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 Adleman Leonard November Molecular computation of solutions to combinatorial problems Science 266 5187 1021 1024 JSTOR 2885489 PMID 7973651 doi 10 1126 science 7973651 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 Plesnik 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 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 vease el historial la primera version y la ultima 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 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 Datos Q987652 Multimedia Hamiltonian path problem Obtenido de https es wikipedia org w index php title Problema del camino Hamiltoniano amp oldid 135029371, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos