trayectoria hamiltoniana

En el campo matemático de la teoría de grafos , un camino hamiltoniano (o camino trazable ) es un camino en un grafo dirigido o no dirigido que visita cada vértice exactamente una vez. Un ciclo hamiltoniano (o circuito hamiltoniano ) es un ciclo que visita cada vértice exactamente una vez. Un camino hamiltoniano que comienza y termina en vértices adyacentes se puede completar añadiendo una arista más para formar un ciclo hamiltoniano, y la eliminación de cualquier arista de un ciclo hamiltoniano produce un camino hamiltoniano. Los problemas computacionales para determinar si tales caminos y ciclos existen en grafos son NP-completos ; véase el problema del camino hamiltoniano para más detalles.

Los caminos y ciclos hamiltonianos reciben su nombre de William Rowan Hamilton , quien inventó el juego icosiano , también conocido como el rompecabezas de Hamilton , que consiste en encontrar un ciclo hamiltoniano en el grafo de aristas del dodecaedro . Hamilton resolvió este problema utilizando el cálculo icosiano , una estructura algebraica basada en raíces de la unidad con muchas similitudes con los cuaterniones (también inventados por Hamilton). Esta solución no se generaliza a grafos arbitrarios.

A pesar de haber recibido su nombre en honor a Hamilton, los ciclos hamiltonianos en poliedros ya habían sido estudiados un año antes por Thomas Kirkman , quien, en particular, dio un ejemplo de un poliedro sin ciclos hamiltonianos. ^{[ 1 ]} Incluso antes, los ciclos y caminos hamiltonianos en el grafo del caballo del tablero de ajedrez , el recorrido del caballo , habían sido estudiados en el siglo IX en las matemáticas indias por Rudrata , y casi al mismo tiempo en las matemáticas islámicas por al-Adli ar-Rumi . En la Europa del siglo XVIII, los recorridos del caballo fueron publicados por Abraham de Moivre y Leonhard Euler . ^{[ 2 ]}

Definiciones

Un camino hamiltoniano o camino trazable es un camino que visita cada vértice del grafo exactamente una vez. Un grafo que contiene un camino hamiltoniano se denomina grafo trazable . Un grafo es hamiltoniano-conexo si para cada par de vértices existe un camino hamiltoniano entre ellos.

Un ciclo hamiltoniano , circuito hamiltoniano , recorrido de vértices o ciclo de grafo es un ciclo que visita cada vértice exactamente una vez. Un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano .

Se pueden definir nociones similares para grafos dirigidos , donde cada arista (arco) de un camino o ciclo solo se puede trazar en una única dirección (es decir, los vértices están conectados con flechas y las aristas se trazan "de la cola a la cabeza").

Una descomposición hamiltoniana es una descomposición de un grafo en circuitos hamiltonianos mediante sus aristas.

Un laberinto hamiltoniano es un tipo de rompecabezas lógico cuyo objetivo es encontrar el ciclo hamiltoniano único en un grafo dado. ^{[ 3 ]}^{[ 4 ]}

Ejemplos

Un grafo completo con más de dos vértices es hamiltoniano.
Cada gráfico cíclico es hamiltoniano.
Cada torneo tiene un número impar de caminos hamiltonianos ( Rédei 1934).
Todo sólido platónico , considerado como un grafo, es hamiltoniano ^{[ 5 ].}
El grafo de Cayley de un grupo de Coxeter finito es hamiltoniano (véase la conjetura de Lovász para una afirmación más general).
Los grafos de Cayley en grupos nilpotentes con subgrupo conmutador cíclico son hamiltonianos. ^{[ 6 ]}
El grafo de inversión de un polígono convexo o, equivalentemente, el grafo de rotación de árboles binarios , es hamiltoniano. ^{[ 7 ]}^{[ 8 ]}

Propiedades

Cualquier ciclo hamiltoniano puede convertirse en un camino hamiltoniano eliminando una de sus aristas, pero un camino hamiltoniano solo puede extenderse a un ciclo hamiltoniano si sus extremos son adyacentes.

Todos los grafos hamiltonianos son biconexos , pero un grafo biconexo no tiene por qué ser hamiltoniano (véase, por ejemplo, el grafo de Petersen ). ^{[ 9 ]}

Un grafo euleriano $G$ (un grafo conexo en el que cada vértice tiene grado par) necesariamente tiene un recorrido euleriano, un camino cerrado que pasa por cada arista de $G$ exactamente una vez. Este recorrido corresponde a un ciclo hamiltoniano en el grafo de líneas $L (G)$ , por lo que el grafo de líneas de todo grafo euleriano es hamiltoniano. Los grafos de líneas pueden tener otros ciclos hamiltonianos que no corresponden a recorridos eulerianos, y en particular, el grafo de líneas $L (G)$ de todo grafo hamiltoniano $G$ es en sí mismo hamiltoniano, independientemente de si el grafo $G$ es euleriano. ^{[ 10 ]}

Un torneo (con más de dos vértices) es hamiltoniano si y solo si es fuertemente conectado .

El número de ciclos hamiltonianos diferentes en un grafo completo no dirigido de $n$ vértices es $($ $n - 1)! / 2 ⁠$ y en un grafo completo dirigido de $n$ vértices es $(n - 1)!$ . Estos recuentos suponen que los ciclos que son iguales salvo por su punto de partida no se cuentan por separado.

Teorema de Bondy-Chvátal

La mejor caracterización del grado de vértice de los grafos hamiltonianos fue proporcionada en 1972 por el teorema de Bondy - Chvátal , que generaliza resultados anteriores de GA Dirac (1952) y Øystein Ore . Ambos teoremas, el de Dirac y el de Ore, también pueden derivarse del teorema de Pósa (1962). La hamiltonicidad ha sido ampliamente estudiada en relación con varios parámetros como la densidad del grafo , la tenacidad , los subgrafos prohibidos y la distancia , entre otros parámetros. ^{[ 11 ]} Los teoremas de Dirac y Ore básicamente establecen que un grafo es hamiltoniano si tiene suficientes aristas .

El teorema de Bondy-Chvátal opera sobre el cierre $cl(G)$ de un grafo $G$ con $n$ vértices, obtenido agregando repetidamente una nueva arista $uv$ que conecta un par de vértices no adyacentes $u$ y $v$ con $deg(v) + deg(u) \geq n$ hasta que no se puedan encontrar más pares con esta propiedad.

Teorema de Bondy-Chvátal (1976) : Un grafo es hamiltoniano si y solo si su clausura es hamiltoniana.

Como los grafos completos son hamiltonianos, todos los grafos cuya clausura es completa son hamiltonianos, que es el contenido de los siguientes teoremas anteriores de Dirac y Ore.

Teorema de Dirac (1952) — Un grafo simple con $n$ vértices ( $n\geq 3$ ) es hamiltoniano si cada vértice tiene grado ${\tfrac {n}{2}}$ o mayor.

Teorema de Ore (1960) — Un grafo simple con $n$ vértices ( $n\geq 3$ ) es hamiltoniano si, para cada par de vértices no adyacentes, la suma de sus grados es $n$ o mayor.

Los siguientes teoremas pueden considerarse versiones dirigidas:

Ghouila–Houiri (1960) — Un grafo dirigido simple fuertemente conectado con $n$ vértices es hamiltoniano si cada vértice tiene un grado completo mayor o igual a $n$ .

Meyniel (1973) — Un grafo dirigido simple fuertemente conexo con $n$ vértices es hamiltoniano si la suma de los grados completos de cada par de vértices distintos no adyacentes es mayor o igual que $2n-1$

El número de vértices debe duplicarse porque cada arista no dirigida corresponde a dos arcos dirigidos y, por lo tanto, el grado de un vértice en el grafo dirigido es el doble del grado en el grafo no dirigido.

Rahman– Kaykobad (2005) — Un grafo simple con $n$ vértices tiene un camino hamiltoniano si, para cada par de vértices no adyacentes, la suma de sus grados y la longitud de su camino más corto es mayor que $n$ . ^{[ 12 ]}

El teorema anterior solo puede reconocer la existencia de un camino hamiltoniano en un grafo, pero no un ciclo hamiltoniano.

Muchos de estos resultados tienen análogos para grafos bipartitos equilibrados , en los que los grados de los vértices se comparan con el número de vértices en un solo lado de la bipartición en lugar del número de vértices en todo el grafo. ^{[ 13 ]}

Existencia de ciclos hamiltonianos en grafos planares

Teorema : Una triangulación planar 4-conexa tiene un ciclo hamiltoniano. ^{[ 14 ]}

Teorema : Un grafo planar 4-conexo tiene un ciclo hamiltoniano. ^{[ 15 ]}

El polinomio del ciclo hamiltoniano

Una representación algebraica de los ciclos hamiltonianos de un digrafo ponderado dado (cuyos arcos tienen pesos asignados a partir de un cierto campo base) es el polinomio del ciclo hamiltoniano de su matriz de adyacencia ponderada, definido como la suma de los productos de los pesos de los arcos de los ciclos hamiltonianos del digrafo. Este polinomio no es idénticamente cero como función de los pesos de los arcos si y solo si el digrafo es hamiltoniano. Grigoriy Kogan demostró la relación entre la complejidad computacional de su cálculo y el cálculo del permanente . ^{[ 16 ]}

Véase también

La conjetura de Barnette , un problema abierto sobre la hamiltonicidad de los grafos poliédricos bipartitos cúbicos.
Camino euleriano , un camino que pasa por todas las aristas de un grafo.
Teorema de Fleischner sobre cuadrados hamiltonianos de grafos
Código gris
El teorema de Grinberg proporciona una condición necesaria para que los grafos planares tengan un ciclo hamiltoniano.
Problema de la trayectoria hamiltoniana , el problema computacional de encontrar trayectorias hamiltonianas.
Grafo hipohamiltoniano , un grafo no hamiltoniano en el que cada subgrafo al que se le eliminan vértices es hamiltoniano.
Recorrido del caballo , un ciclo hamiltoniano en el grafo del caballo.
Notación LCF para grafos cúbicos hamiltonianos .
Conjetura de Lovász de que los grafos transitivos en vértices son hamiltonianos.
Grafo pancíclico , grafos con ciclos de todas las longitudes, incluyendo un ciclo hamiltoniano.
Panconectividad , un fortalecimiento tanto de la panciclicidad como de la conectividad hamiltoniana.
Los siete puentes de Königsberg
Exponente de brevedad , una medida numérica de cuán lejos del hamiltoniano pueden estar los gráficos de una familia.
Serpiente en la caja , el camino inducido más largo en un hipercubo.
Algoritmo de Steinhaus-Johnson-Trotter para encontrar un camino hamiltoniano en un permutoedro
Grafo subhamiltoniano , un subgrafo de un grafo hamiltoniano planar.
La conjetura de Tait (ahora se sabe que es falsa) de que los grafos poliédricos 3-regulares son hamiltonianos.
El problema del viajante
Los grafos de Harris son una familia de grafos robustos, eulerianos y no hamiltonianos.

Notas

↑ Biggs, NL (1981), "TP Kirkman, matemático", The Bulletin of the London Mathematical Society , 13 (2): 97–120 , doi : 10.1112/blms/13.2.97 , MR 0608093 .
↑ Watkins, John J. (2004), "Capítulo 2: Recorridos del caballo", Across the Board: The Mathematics of Chessboard Problems , Princeton University Press, pp. 25–38 , ISBN 978-0-691-15498-5.
↑ de Ruiter, Johan (2017). Laberintos de Hamilton: la guía para principiantes .
↑ Friedman, Erich. "Laberintos hamiltonianos" . Erich's Puzzle Palace . Archivado del original el 16 de abril de 2016. Consultado el 23 de octubre de 2025 .
↑ Gardner, M. «Juegos matemáticos: Acerca de la notable similitud entre el juego icosiano y las torres de Hanoi». Sci. Amer. 196, 150–156, mayo de 1957
↑ Ghaderpour, E.; Morris, DW (2014). "Los grafos de Cayley en grupos nilpotentes con subgrupo conmutador cíclico son hamiltonianos". Ars Mathematica Contemporanea . 7 (1): 55– 72. arXiv : 1111.6216 . doi : 10.26493/1855-3974.280.8d3 . S2CID 57575227 .
↑ Lucas, Joan M. (1987), "El grafo de rotación de árboles binarios es hamiltoniano", Journal of Algorithms , 8 (4): 503– 535, doi : 10.1016/0196-6774(87)90048-4
↑ Hurtado, Ferran ; Noy, Marc (1999), "Grafo de triangulaciones de un polígono convexo y árbol de triangulaciones", Geometría Computacional , 13 (3): 179–188 , doi : 10.1016/S0925-7721(99)00016-4
↑ Eric W. Weisstein . "Grafo biconectado" . Wolfram MathWorld.
↑ Balakrishnan, R.; Ranganathan, K. (2012), "Corolario 6.5.5", A Textbook of Graph Theory , Springer, pág. 134, ISBN 9781461445296.
↑ Gould, Ronald J. (8 de julio de 2002). "Avances sobre el problema hamiltoniano: una revisión" (PDF) . Universidad de Emory. Archivado del original (PDF) el 13 de julio de 2018. Recuperado el 10 de diciembre de 2012 .
↑ Rahman, MS; Kaykobad, M. (abril de 2005). "Sobre ciclos hamiltonianos y caminos hamiltonianos". Information Processing Letters . 94 : 37–41 . doi : 10.1016/j.ipl.2004.12.002 .
↑Moon, J.; Moser, L. (1963), "On Hamiltonian bipartite graphs", Israel Journal of Mathematics, 1 (3): 163–165, doi:10.1007/BF02759704, MR 0161332, S2CID 119358798
↑Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics, Second Series, 32 (2): 378–390, doi:10.2307/1968197, JSTOR 1968197, MR 1503003
↑Tutte, W. T. (1956), "A theorem on planar graphs", Trans. Amer. Math. Soc., 82: 99–116, doi:10.1090/s0002-9947-1956-0081471-8
↑Kogan, Grigoriy (1996). "Computing permanents over fields of characteristic 3: Where and why it becomes difficult". Proceedings of 37th Conference on Foundations of Computer Science. pp. 108–114. doi:10.1109/SFCS.1996.548469. ISBN 0-8186-7594-2. S2CID 39024286.

References

Berge, Claude; Ghouila-Houiri, A. (1962), Programming, games and transportation networks, New York: Sons, Inc.
DeLeon, Melissa (2000), "A study of sufficient conditions for Hamiltonian cycles"(PDF), Rose-Hulman Undergraduate Math Journal, 1 (1), archived from the original(PDF) on 2012-12-22, retrieved 2005-11-28.
Dirac, G. A. (1952), "Some theorems on abstract graphs", Proceedings of the London Mathematical Society, 3rd Ser., 2: 69–81, doi:10.1112/plms/s3-2.1.69, MR 0047308.
Hamilton, William Rowan (1856), "Memorandum respecting a new system of roots of unity", Philosophical Magazine, 12: 446.
Hamilton, William Rowan (1858), "Account of the Icosian Calculus", Proceedings of the Royal Irish Academy, 6: 415–416.
Meyniel, M. (1973), "Une condition suffisante d'existence d'un circuito hamiltonien dans un graphe orienté", Journal of Combinatorial Theory , Serie B, 14 (2): 137– 147, doi : 10.1016/0095-8956(73)90057-9 , MR 0317997 .
Ore, Øystein (1960), "Nota sobre circuitos hamiltonianos", The American Mathematical Monthly , 67 (1): 55, doi : 10.2307/2308928 , JSTOR 2308928 , MR 0118683 .
Pósa, L. (1962), "Un teorema sobre las líneas de Hamilton", Magyar Tud. Akád. Estera. Aeropuerto Internacional de Kutató. Kozl. , 7 : 225– 226, SEÑOR 0184876 .

Enlaces externos

Weisstein, Eric W. "Ciclo hamiltoniano" . MathWorld .
El recorrido de Euler y los ciclos de Hamilton

[1] Biggs, NL (1981), "TP Kirkman, matemático", The Bulletin of the London Mathematical Society , 13 (2): 97–120 , doi : 10.1112/blms/13.2.97 , MR 0608093 .

[2] Watkins, John J. (2004), "Capítulo 2: Recorridos del caballo", Across the Board: The Mathematics of Chessboard Problems , Princeton University Press, pp. 25–38 , ISBN 978-0-691-15498-5.

[3] Ruiter, Johan (2017). Laberintos de Hamilton: la guía para principiantes .

[4] Friedman, Erich. "Laberintos hamiltonianos" . Erich's Puzzle Palace . Archivado del original el 16 de abril de 2016. Consultado el 23 de octubre de 2025 .

[5] Gardner, M. «Juegos matemáticos: Acerca de la notable similitud entre el juego icosiano y las torres de Hanoi». Sci. Amer. 196, 150–156, mayo de 1957

[6] Ghaderpour, E.; Morris, DW (2014). "Los grafos de Cayley en grupos nilpotentes con subgrupo conmutador cíclico son hamiltonianos". Ars Mathematica Contemporanea . 7 (1): 55– 72. arXiv : 1111.6216 . doi : 10.26493/1855-3974.280.8d3 . S2CID 57575227 .

[7] Lucas, Joan M. (1987), "El grafo de rotación de árboles binarios es hamiltoniano", Journal of Algorithms , 8 (4): 503– 535, doi : 10.1016/0196-6774(87)90048-4

[8] Hurtado, Ferran ; Noy, Marc (1999), "Grafo de triangulaciones de un polígono convexo y árbol de triangulaciones", Geometría Computacional , 13 (3): 179–188 , doi : 10.1016/S0925-7721(99)00016-4

[9] Eric W. Weisstein . "Grafo biconectado" . Wolfram MathWorld.

[10] Balakrishnan, R.; Ranganathan, K. (2012), "Corolario 6.5.5", A Textbook of Graph Theory , Springer, pág. 134, ISBN 9781461445296.

[11] Gould, Ronald J. (8 de julio de 2002). "Avances sobre el problema hamiltoniano: una revisión" (PDF) . Universidad de Emory. Archivado del original (PDF) el 13 de julio de 2018. Recuperado el 10 de diciembre de 2012 .

[12] Rahman, MS; Kaykobad, M. (abril de 2005). "Sobre ciclos hamiltonianos y caminos hamiltonianos". Information Processing Letters . 94 : 37–41 . doi : 10.1016/j.ipl.2004.12.002 .

[13] Moon, J.; Moser, L. (1963), "On Hamiltonian bipartite graphs", Israel Journal of Mathematics, 1 (3): 163–165, doi:10.1007/BF02759704, MR 0161332, S2CID 119358798

[14] Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics, Second Series, 32 (2): 378–390, doi:10.2307/1968197, JSTOR 1968197, MR 1503003

[15] Tutte, W. T. (1956), "A theorem on planar graphs", Trans. Amer. Math. Soc., 82: 99–116, doi:10.1090/s0002-9947-1956-0081471-8

[16] Kogan, Grigoriy (1996). "Computing permanents over fields of characteristic 3: Where and why it becomes difficult". Proceedings of 37th Conference on Foundations of Computer Science. pp. 108–114. doi:10.1109/SFCS.1996.548469. ISBN 0-8186-7594-2. S2CID 39024286.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ].

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]