Camino hamiltoniano

Ruta en un gráfico que visita cada vértice exactamente una vez

Un ciclo hamiltoniano alrededor de una red de seis vértices

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 agregando 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 ; consulte el problema del camino hamiltoniano para obtener más detalles.

Los caminos y ciclos hamiltonianos reciben su nombre de William Rowan Hamilton , quien inventó el juego icosiano , ahora también conocido como el rompecabezas de Hamilton , que consiste en encontrar un ciclo hamiltoniano en el gráfico 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 gráficos arbitrarios.

A pesar de que llevan el nombre de Hamilton, los ciclos hamiltonianos en poliedros también 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 aproximadamente 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 llama grafo trazable . Un grafo es hamiltoniano-conexo si para cada par de vértices hay un camino hamiltoniano entre los dos vértices.

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 gráficos dirigidos , donde cada borde (arco) de una trayectoria o ciclo solo se puede trazar en una única dirección (es decir, los vértices están conectados con flechas y los bordes se trazan "de cola a cabeza").

Una descomposición hamiltoniana es una descomposición de los bordes de un gráfico en circuitos hamiltonianos.

Un laberinto de Hamilton es un tipo de rompecabezas lógico en el que el objetivo es encontrar el ciclo hamiltoniano único en un gráfico dado. ^[3]^[4]

Ejemplos

Un gráfico completo con más de dos vértices es hamiltoniano
Todo gráfico de ciclo 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 gráfico de Cayley de un grupo de Coxeter finito es hamiltoniano (para obtener más información sobre las trayectorias hamiltonianas en los gráficos de Cayley, consulte la conjetura de Lovász ).
Los gráficos de Cayley en grupos nilpotentes con subgrupo conmutador cíclico son hamiltonianos. ^[6]
El gráfico de rotación de un polígono convexo o, equivalentemente, el gráfico de rotación de árboles binarios , es hamiltoniano. ^[7]^[8]

Propiedades

Cualquier ciclo hamiltoniano se puede convertir en un camino hamiltoniano eliminando uno de sus bordes, pero un camino hamiltoniano se puede extender a un ciclo hamiltoniano solo si sus puntos finales son adyacentes.

Todos los grafos hamiltonianos son biconexos , pero un grafo biconexo no necesita 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 de Euler, un recorrido cerrado que pasa por cada arista de $G$ exactamente una vez. Este recorrido corresponde a un ciclo hamiltoniano en el grafo lineal $L (G)$ , por lo que el grafo lineal de cada grafo euleriano es hamiltoniano. Los grafos lineales pueden tener otros ciclos hamiltonianos que no corresponden a los recorridos de Euler y, en particular, el grafo lineal $L (G)$ de cada 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 sólo si está fuertemente conexo .

El número de ciclos hamiltonianos diferentes en un grafo completo no dirigido en $n$ vértices $es (n - 1)! / 2 ⁠$ y en un grafo dirigido completo en $n$ vértices es $(n - 1)!$ . Estos conteos suponen que los ciclos que son iguales aparte de 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 . Tanto el teorema de Dirac como 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 establecen básicamente 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 añadiendo 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 sólo si su cierre es hamiltoniano.

Como los grafos completos son hamiltonianos, todos los grafos cuyo cierre es completo 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 ( ) es hamiltoniano si cada vértice tiene grado o mayor. $n\geq 3$ ${\frac {n}{2}}$

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

Los siguientes teoremas pueden considerarse versiones dirigidas:

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

Meyniel (1973) — Un gráfico dirigido simple fuertemente conectado 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 a ${\estilo de visualización 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 gráfico dirigido es el doble del grado en el gráfico no dirigido.

Rahman– Kaykobad (2005) — Un gráfico simple con $n$ vértices tiene una trayectoria hamiltoniana si, para cada par de vértices no adyacentes, la suma de sus grados y la longitud de su trayectoria más corta es mayor que $n$ . ^[12]

El teorema anterior sólo puede reconocer la existencia de una trayectoria hamiltoniana en un gráfico y no de un ciclo hamiltoniano.

Muchos de estos resultados tienen análogos para los gráficos 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 gráfico. ^[13]

Existencia de ciclos hamiltonianos en grafos planares

Teorema : Una triangulación planar con 4 conexiones tiene un ciclo hamiltoniano. ^[14]

Teorema : Un gráfico plano con 4 conexiones tiene un ciclo hamiltoniano. ^[15]

El polinomio del ciclo hamiltoniano

Una representación algebraica de los ciclos hamiltonianos de un dígrafo ponderado dado (cuyos arcos tienen pesos asignados a partir de un cierto campo de base) es el polinomio del ciclo hamiltoniano de su matriz de adyacencia ponderada definida como la suma de los productos de los pesos de los arcos de los ciclos hamiltonianos del dígrafo. Este polinomio no es idénticamente cero como función de los pesos de los arcos si y solo si el dígrafo es hamiltoniano. La relación entre las complejidades computacionales de calcularlo y calcular el permanente fue demostrada por Grigoriy Kogan. ^[16]

Véase también

Conjetura de Barnette , un problema abierto sobre la hamiltonicidad de grafos poliédricos cúbicos bipartitos
Camino euleriano , un camino que pasa por todos los bordes de un gráfico
Teorema de Fleischner sobre los cuadrados hamiltonianos de los grafos
Código gris
Teorema de Grinberg que proporciona una condición necesaria para que los gráficos 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 con vértice eliminado es hamiltoniano
Recorrido del caballo , un ciclo hamiltoniano en el grafo del caballo
Notación LCF para gráficos cúbicos hamiltonianos .
Conjetura de Lovász de que los grafos transitivos de vértice son hamiltonianos
Gráfico pancíclico , gráficos con ciclos de todas las longitudes, incluido 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 qué tan 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 hallar una trayectoria hamiltoniana en un permutoedro
Gráfico subhamiltoniano , un subgrafo de un gráfico hamiltoniano plano
Conjetura de Tait (ahora conocida como falsa) de que los grafos poliédricos 3-regulares son hamiltonianos
Problema del viajante de comercio

Notas

^ Biggs, NL (1981), "TP Kirkman, matemático", Boletín de la Sociedad Matemática de Londres , 13 (2): 97–120, doi :10.1112/blms/13.2.97, MR 0608093.
^ Watkins, John J. (2004), "Capítulo 2: Giras del caballo", Across the Board: The Mathematics of Chessboard Problems , Princeton University Press, págs. 25-38, ISBN 978-0-691-15498-5.
^ de Ruiter, Johan (2017). Laberintos de Hamilton: la guía para principiantes .
^ Friedman, Erich (2009). "Laberintos hamiltonianos". El palacio de los rompecabezas de Erich . Archivado desde el original el 16 de abril de 2016. Consultado el 27 de mayo de 2017 .
^ Gardner, M. "Juegos matemáticos: acerca de la notable similitud entre el juego de Icos 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 gráfico 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), "Gráfico de triangulaciones de un polígono convexo y árbol de triangulaciones", Computational Geometry , 13 (3): 179–188, doi : 10.1016/S0925-7721(99)00016-4
^ Eric Weinstein. "Grafo biconexo". Wolfram MathWorld.
^ Balakrishnan, R.; Ranganathan, K. (2012), "Corolario 6.5.5", Un libro de texto de teoría de grafos, Springer, pág. 134, ISBN 9781461445296.
^ Gould, Ronald J. (8 de julio de 2002). "Avances en el problema hamiltoniano: una encuesta" (PDF) . Universidad Emory. Archivado desde el original (PDF) el 2018-07-13 . Consultado el 2012-12-10 .
^ 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), "Sobre los grafos bipartitos hamiltonianos", Israel Journal of Mathematics , 1 (3): 163–165, doi :10.1007/BF02759704, MR 0161332, S2CID 119358798
^ Whitney, Hassler (1931), "Un teorema sobre grafos", Anales de Matemáticas , Segunda serie, 32 (2): 378–390, doi :10.2307/1968197, JSTOR 1968197, MR 1503003
^ Tutte, WT (1956), "Un teorema sobre grafos planos", Trans. Amer. Math. Soc. , 82 : 99–116, doi : 10.1090/s0002-9947-1956-0081471-8
^ Kogan, Grigoriy (1996). "Cálculo de permanentes sobre cuerpos de característica 3: dónde y por qué resulta difícil". Actas de la 37.ª Conferencia sobre Fundamentos de la Ciencia de la Computación . pp. 108–114. doi :10.1109/SFCS.1996.548469. ISBN . 0-8186-7594-2. Número de identificación del sujeto 39024286.

Referencias

Berge, Claude ; Ghouila-Houiri, A. (1962), Programación, juegos y redes de transporte , Nueva York: Sons, Inc.
DeLeon, Melissa (2000), "Un estudio de condiciones suficientes para ciclos hamiltonianos" (PDF) , Rose-Hulman Undergraduate Math Journal , 1 (1), archivado desde el original (PDF) el 22 de diciembre de 2012 , consultado el 28 de noviembre de 2005.
Dirac, GA (1952), "Algunos teoremas sobre grafos abstractos", Actas de la London Mathematical Society , 3.ª serie, 2 : 69–81, doi :10.1112/plms/s3-2.1.69, MR 0047308.
Hamilton, William Rowan (1856), "Memorando sobre un nuevo sistema de raíces de unidad", Philosophical Magazine , 12 : 446.
Hamilton, William Rowan (1858), "Explicación del cálculo icosiano", Actas de la Real Academia Irlandesa , 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 , SEÑOR 0317997.
Ore, Øystein (1960), "Nota sobre circuitos de Hamilton", 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 .
La gira de Euler y los ciclos de Hamilton

[1] Biggs, NL (1981), "TP Kirkman, matemático", Boletín de la Sociedad Matemática de Londres , 13 (2): 97–120, doi :10.1112/blms/13.2.97, MR 0608093.

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

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

[4] Friedman, Erich (2009). "Laberintos hamiltonianos". El palacio de los rompecabezas de Erich . Archivado desde el original el 16 de abril de 2016. Consultado el 27 de mayo de 2017 .

[5] Gardner, M. "Juegos matemáticos: acerca de la notable similitud entre el juego de Icos 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 gráfico 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), "Gráfico de triangulaciones de un polígono convexo y árbol de triangulaciones", Computational Geometry , 13 (3): 179–188, doi : 10.1016/S0925-7721(99)00016-4

[9] Eric Weinstein. "Grafo biconexo". Wolfram MathWorld.

[10] Balakrishnan, R.; Ranganathan, K. (2012), "Corolario 6.5.5", Un libro de texto de teoría de grafos, Springer, pág. 134, ISBN 9781461445296.

[11] Gould, Ronald J. (8 de julio de 2002). "Avances en el problema hamiltoniano: una encuesta" (PDF) . Universidad Emory. Archivado desde el original (PDF) el 2018-07-13 . Consultado el 2012-12-10 .

[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), "Sobre los grafos bipartitos hamiltonianos", Israel Journal of Mathematics , 1 (3): 163–165, doi :10.1007/BF02759704, MR 0161332, S2CID 119358798

[14] Whitney, Hassler (1931), "Un teorema sobre grafos", Anales de Matemáticas , Segunda serie, 32 (2): 378–390, doi :10.2307/1968197, JSTOR 1968197, MR 1503003

[15] Tutte, WT (1956), "Un teorema sobre grafos planos", Trans. Amer. Math. Soc. , 82 : 99–116, doi : 10.1090/s0002-9947-1956-0081471-8

[16] Kogan, Grigoriy (1996). "Cálculo de permanentes sobre cuerpos de característica 3: dónde y por qué resulta difícil". Actas de la 37.ª Conferencia sobre Fundamentos de la Ciencia de la Computación . pp. 108–114. doi :10.1109/SFCS.1996.548469. ISBN . 0-8186-7594-2. Número de identificación del sujeto 39024286.