En el campo matemático de la teoría de grafos , un camino hamiltoniano (o camino rastreable ) es un camino en un gráfico dirigido o no dirigido que visita cada vértice exactamente una vez. Un ciclo hamiltoniano (o circuito hamiltoniano ) es un camino hamiltoniano que es un ciclo . Determinar si tales trayectorias y ciclos existen en los gráficos es el problema de la trayectoria hamiltoniana , que es NP-completo .
Los caminos y ciclos hamiltonianos llevan el nombre de William Rowan Hamilton, quien inventó el juego icosiano , ahora también conocido como el rompecabezas de Hamilton , que implica encontrar un ciclo hamiltoniano en el gráfico de borde del dodecaedro . Hamilton resolvió este problema utilizando el cálculo icosiano , una estructura algebraica basada en raíces de unidad con muchas similitudes con los cuaterniones (también inventado por Hamilton). Esta solución no se generaliza a gráficos arbitrarios.
A pesar de llevar 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 poliedro sin ciclos hamiltonianos. [1] Incluso antes, los ciclos y caminos hamiltonianos en el gráfico del caballo del tablero de ajedrez , el recorrido del caballero , 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, las giras de los caballeros fueron publicadas por Abraham de Moivre y Leonhard Euler . [2]
Definiciones
Una ruta hamiltoniana o trazable es una ruta que visita cada vértice del gráfico exactamente una vez. Una gráfica que contiene una ruta hamiltoniana se denomina gráfica trazable . Una gráfica está conectada al hamiltoniano si por cada par de vértices hay un camino hamiltoniano entre los dos vértices.
Un ciclo hamiltoniano , circuito hamiltoniano , recorrido de vértice o ciclo de gráfico es un ciclo que visita cada vértice exactamente una vez. Un gráfico que contiene un ciclo hamiltoniano se llama gráfico hamiltoniano .
Se pueden definir nociones similares para gráficos dirigidos , donde cada borde (arco) de una ruta o ciclo solo se puede trazar en una sola dirección (es decir, los vértices están conectados con flechas y los bordes trazados "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 acertijo lógico en el que el objetivo es encontrar el ciclo hamiltoniano único en un gráfico determinado. [3] [4]
Ejemplos de
- Un gráfico completo con más de dos vértices es hamiltoniano
- Cada 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 gráfico, es hamiltoniano [5]
- El gráfico de Cayley de un grupo de Coxeter finito es hamiltoniano (para obtener más información sobre los caminos hamiltonianos en los gráficos de Cayley, consulte la conjetura de Lovász ).
Propiedades
Cualquier ciclo hamiltoniano se puede convertir en una ruta hamiltoniana eliminando uno de sus bordes, pero una ruta hamiltoniana puede extenderse a un ciclo hamiltoniano solo si sus puntos finales son adyacentes.
Todos los gráficos hamiltonianos están biconectados , pero no es necesario que un gráfico biconectado sea hamiltoniano (ver, por ejemplo, el gráfico de Petersen ). [6]
Un gráfico euleriano G (un gráfico conectado en el que cada vértice tiene un grado par) necesariamente tiene un recorrido de Euler, un paseo cerrado que pasa por cada borde de G exactamente una vez. Este recorrido corresponde a un ciclo hamiltoniano en el gráfico lineal L ( G ), por lo que el gráfico lineal de cada gráfico euleriano es hamiltoniano. Los gráficos lineales pueden tener otros ciclos hamiltonianos que no se corresponden con los recorridos de Euler y, en particular, el gráfico lineal L ( G ) de cada gráfico hamiltoniano G es en sí mismo hamiltoniano, independientemente de si el gráfico G es euleriano. [7]
Un torneo (con más de dos vértices) es hamiltoniano si y solo si está fuertemente conectado .
El número de ciclos hamiltonianos diferentes en un gráfico completo no dirigido en n vértices esy en un grafo dirigido completo en n vértices es. Estos recuentos asumen 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 gráficos hamiltonianos fue proporcionada en 1972 por el teorema de Bondy - Chvátal , que generaliza los resultados anteriores de GA Dirac (1952) y Øystein Ore . Tanto los teoremas de Dirac como los 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 gráfico , la tenacidad , los subgrafos prohibidos y la distancia, entre otros parámetros. [8] Los teoremas de Dirac y Ore básicamente establecen que una gráfica es hamiltoniana si tiene suficientes aristas .
El Bondy-Chvátal teorema opera sobre el cierre cl ( G ) de un gráfico de G con n vértices, obtenido añadiendo repetidamente un nuevo borde uv conexión de un no adyacente par de vértices u y v con deg ( v ) + deg ( u ) ≥ n hasta que no se puedan encontrar más pares con esta propiedad.
- Teorema de Bondy-Chvátal (1976). Un gráfico es hamiltoniano si y solo si su cierre es hamiltoniano.
Como los gráficos completos son hamiltonianos, todos los gráficos cuyo cierre es completo son hamiltonianos, que es el contenido de los siguientes teoremas anteriores de Dirac y Ore.
- Teorema de Dirac (1952). Un gráfico simple con n vértices ( ) es hamiltoniano si cada vértice tiene grado o mayor.
- Teorema de Ore (1960). Un gráfico 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.
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 que n .
- Meyniel (1973). Un grafo dirigido simple fuertemente conectado con n vértices es hamiltoniano si la suma de los grados completos de cada par de vértices no adyacentes distintos es mayor o igual a .
El número de vértices debe duplicarse porque cada borde no dirigido 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 ruta hamiltoniana si, para cada par de vértices no adyacentes, la suma de sus grados y la longitud de su ruta más corta es mayor que n . [9]
El teorema anterior solo puede reconocer la existencia de una trayectoria hamiltoniana en un gráfico y no un ciclo hamiltoniano.
Muchos de estos resultados tienen análogos para los gráficos bipartitos balanceados , 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. [10]
Existencia de ciclos hamiltonianos en gráficos planares
- Teorema (Whitney, 1931)
- Una triangulación plana de 4 conexiones tiene un ciclo hamiltoniano.
- Teorema (Tutte, 1956)
- Un gráfico plano de 4 conexiones tiene un ciclo hamiltoniano.
El polinomio del ciclo hamiltoniano
Una representación algebraica de los ciclos hamiltonianos de un dígrafo ponderado dado (a cuyos arcos se les asignan pesos de un determinado campo de tierra) es el polinomio del ciclo hamiltoniano de su matriz de adyacencia ponderada definida como la suma de los productos de los pesos de arco de los ciclos hamiltonianos del dígrafo. . Este polinomio no es idénticamente cero como función en los pesos del arco si y solo si el dígrafo es hamiltoniano. La relación entre las complejidades computacionales de calcularlo y calcular el permanente se mostró en Kogan (1996) .
Ver también
- Conjetura de Barnette , un problema abierto sobre hamiltonicidad de grafos poliédricos bipartitos cúbicos
- Camino euleriano , un camino a través de todos los bordes en un gráfico
- Teorema de Fleischner , sobre cuadrados de gráficos hamiltonianos
- Código gris
- El teorema de Grinberg que da una condición necesaria para que los gráficos planos tengan un ciclo hamiltoniano
- Problema del camino hamiltoniano , el problema computacional de encontrar caminos hamiltonianos
- Gráfico hipohamiltoniano , un gráfico no hamiltoniano en el que cada subgráfico con vértice eliminado es hamiltoniano
- Tour del caballero , un ciclo hamiltoniano en el gráfico del caballero
- Notación LCF para gráficas cúbicas hamiltonianas .
- Conjetura de Lovász de que los gráficos transitivos de vértice son hamiltonianos
- Gráfico pancíclico , gráficos con ciclos de todas las longitudes, incluido un ciclo hamiltoniano
- Siete puentes de Königsberg
- Exponente de brevedad , una medida numérica de qué tan lejos del hamiltoniano las gráficas de una familia pueden estar
- Snake-in-the-box , 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 conocida como falsa) de que las gráficas poliédricas regulares 3 son hamiltonianas
- Problema del vendedor ambulante
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: Tours de Knight", en todos los ámbitos: Las matemáticas del tablero de ajedrez problemas , 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 (2009). "Laberintos hamiltonianos" . Palacio de 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: sobre la notable similitud entre el juego de Icosian y las torres de Hanoi". Sci. Amer. 196, 150-156, mayo de 1957
- ^ Eric Weinstein. "Gráfico biconectado" . Wolfram MathWorld.
- ^ Balakrishnan, R .; Ranganathan, K. (2012), "Corolario 6.5.5", Un libro de texto de teoría de gráficos , Springer, p. 134, ISBN 9781461445296.
- ^ Gould, Ronald J. (8 de julio de 2002). "Avances en el problema hamiltoniano - una encuesta" (PDF) . Universidad de Emory . Consultado el 10 de diciembre de 2012 .
- ^ Rahman, MS; Kaykobad, M. (abril de 2005). "En ciclos hamiltonianos y caminos hamiltonianos". Cartas de procesamiento de información . 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
Referencias
- Berge, Claude ; Ghouila-Houiri, A. (1962), Programación, juegos y redes de transporte , Nueva York: Sons, Inc.
- DeLeon, Melissa (2000), "Un estudio de las condiciones suficientes para los ciclos hamiltonianos" (PDF) , Rose-Hulman Undergraduate Math Journal , 1 (1), archivado desde el original (PDF) el 2012-12-22 , recuperado 2005- 11-28.
- Dirac, GA (1952), "Algunos teoremas sobre gráficos abstractos", 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), "Memorando sobre un nuevo sistema de raíces de unidad", Philosophical Magazine , 12 : 446.
- Hamilton, William Rowan (1858), "Cuenta del cálculo icosiano", Actas de la Real Academia Irlandesa , 6 : 415–416.
- Meyniel, M. (1973), "Une condition suffisante d'existence d'un circuit 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 los 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. Akad. Estera. Kutató Int. Közl. , 7 : 225–226, MR 0184876.
- Whitney, Hassler (1931), "Un teorema sobre gráficas", Annals of Mathematics , Second Series, 32 (2): 378–390, doi : 10.2307 / 1968197 , JSTOR 1968197 , MR 1503003.
- Tutte, WT (1956), "Un teorema sobre gráficas planas", Trans. Amer. Matemáticas. Soc. , 82 : 99–116, doi : 10.1090 / s0002-9947-1956-0081471-8.
- Kogan, Grigoriy (1996), "Computación permanente sobre campos de característica 3: dónde y por qué se vuelve difícil", 37º Simposio Anual sobre Fundamentos de la Ciencia de la Computación (FOCS '96) : 108-114, doi : 10.1109 / SFCS.1996.548469 , ISBN 0-8186-7594-2
enlaces externos
- Weisstein, Eric W. "Ciclo hamiltoniano" . MathWorld .
- Tour de Euler y ciclos de Hamilton