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. Una ruta hamiltoniana que comienza y termina en vértices adyacentes se puede completar agregando una arista más para formar un ciclo hamiltoniano, y eliminando cualquier arista de un ciclo hamiltoniano produce una ruta hamiltoniana. Los problemas computacionales para determinar si tales caminos y ciclos existen en gráficos son NP-completos ; consulte el problema de la ruta hamiltoniana para obtener más detalles.
Las trayectorias y ciclos hamiltonianos llevan el nombre de William Rowan Hamilton , quien inventó el juego icosiano , ahora también conocido como rompecabezas de Hamilton , que implica 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 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 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 un poliedro sin ciclos hamiltonianos. [1] Incluso antes, los ciclos y trayectorias hamiltonianas en la gráfica del caballo del tablero de ajedrez , el recorrido del caballo , habían sido estudiados en el siglo IX en matemáticas indias por Rudrata , y casi al mismo tiempo en matemáticas islámicas por al-Adli ar-Rumi. . En la Europa del siglo XVIII, Abraham de Moivre y Leonhard Euler publicaron giras de caballeros . [2]
Un camino hamiltoniano o camino trazable es un camino que visita cada vértice del gráfico exactamente una vez. Un gráfico que contiene una trayectoria hamiltoniana se llama gráfico trazable . Un gráfico es hamiltoniano conexo si para cada par de vértices existe un camino hamiltoniano entre los dos vértices.
Un ciclo hamiltoniano , circuito hamiltoniano , recorrido por vértices o ciclo de gráfico es un ciclo que visita cada vértice exactamente una vez. Una gráfica que contiene un ciclo hamiltoniano se llama gráfica hamiltoniana .
Se pueden definir nociones similares para gráficos dirigidos , donde cada borde (arco) de una ruta o ciclo sólo 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 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]
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 gráficos hamiltonianos son biconexos , pero un gráfico biconectado no necesita ser hamiltoniano (ver, por ejemplo, el gráfico de Petersen ). [9]
Un gráfico euleriano G (un gráfico conexo en el que cada vértice tiene un 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 gráfico lineal L ( G ) , por lo que el gráfico lineal de todo gráfico euleriano es hamiltoniano. Los gráficos lineales pueden tener otros ciclos hamiltonianos que no corresponden a 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. [10]
Un torneo (con más de dos vértices) es hamiltoniano si y sólo si está fuertemente conectado .
El número de ciclos hamiltonianos diferentes en un gráfico no dirigido completo en n vértices es( n – 1)!/2¡y en un gráfico dirigido completo en n vértices es ( n – 1)! . Estos conteos suponen que los ciclos que son iguales aparte de su punto de inicio no se cuentan por separado.
La mejor caracterización del grado de vértice de los gráficos hamiltonianos la proporcionó en 1972 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 gráfico , la tenacidad , los subgrafos prohibidos y la distancia, entre otros parámetros. [11] Los teoremas de Dirac y Ore básicamente establecen que un gráfico 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 grados( v ) + grados( u ) ≥ n hasta que no se puedan encontrar más pares con esta propiedad.
Teorema de Bondy-Chvátal (1976) : una gráfica es hamiltoniana si y sólo 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) : una gráfica simple con n vértices ( ) es hamiltoniana si cada vértice tiene un grado o mayor.
Teorema de Ore (1960) : una gráfica simple con n vértices () es hamiltoniana 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 gráfico 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 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
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 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 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 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]
Teorema : una triangulación plana de 4 conexos tiene un ciclo hamiltoniano. [14]
Teorema : un gráfico plano de 4 conexos tiene un ciclo hamiltoniano. [15]
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 terrestre) 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 en los pesos del arco si y sólo si el dígrafo es hamiltoniano. Grigoriy Kogan demostró la relación entre las complejidades computacionales de calcularlo y calcular lo permanente . [dieciséis]
