Un camino hamiltoniano es una secuencia de vértices distintos en un grafo que visita cada vértice exactamente una vez. Si el último vértice del camino es adyacente al primero, forma un ciclo hamiltoniano (también llamado circuito hamiltoniano). El concepto se aplica tanto a grafos no dirigidos como dirigidos: en los grafos dirigidos, cada paso debe seguir la dirección de la arista indicada; en los no dirigidos, las aristas pueden recorrerse en cualquiera de los dos sentidos. Para el contexto formal, véanse recursos básicos sobre grafos y teoría de grafos.

Características clave y diferencias

Los caminos hamiltonianos se centran en visitar vértices sin repetición. Esto contrasta con los caminos eulerianos, que consisten en recorrer cada arista exactamente una vez; ambas nociones son independientes y tienen distintas condiciones necesarias y suficientes, así como algoritmos diferentes. Encontrar un camino hamiltoniano es un problema de decisión: dado un grafo, ¿existe un camino hamiltoniano o un ciclo hamiltoniano? Este problema de decisión es conocido por ser NP-completo en general, un hecho que lo sitúa entre los problemas computacionalmente intratables bajo las hipótesis habituales de la complejidad (NP-completitud). Para comparar con problemas de recorrido basados en aristas, véase material sobre caminos eulerianos.

Ejemplos y clases especiales

Ciertas familias de grafos garantizan comportamiento hamiltoniano. Los grafos completos K_n son hamiltonianos para todo n ≥ 3: cualquier ordenación de los vértices produce un ciclo hamiltoniano. Los torneos (orientaciones de grafos completos) contienen siempre un camino hamiltoniano, resultado conocido como teorema de Rédei. Los árboles solo son hamiltonianos si son ellos mismos caminos: un árbol con alguna ramificación no puede contener un camino hamiltoniano que visite cada vértice exactamente una vez. También existen condiciones suficientes clásicas que aseguran la hamiltonicidad en grafos simples:

  • Teorema de Dirac: un grafo simple con n ≥ 3 vértices es hamiltoniano si todo vértice tiene grado al menos n/2.
  • Teorema de Ore: si cada par de vértices distintos no adyacentes tiene grados cuya suma es al menos n, el grafo es hamiltoniano.

Algoritmos, complejidad y enfoques prácticos

Como el problema general del camino hamiltoniano es NP-completo, no se conoce un algoritmo de tiempo polinómico para todos los grafos. Los algoritmos exactos se basan en tiempo exponencial en el peor caso: entre los ejemplos destacados están la búsqueda con retroceso, la poda y acotación, y enfoques de programación dinámica como el algoritmo de Held–Karp para la formulación del problema del viajante, que se ejecuta en aproximadamente O(n^2 2^n) y se usa con frecuencia como referencia para soluciones exactas. En la práctica, para instancias grandes se emplean heurísticas, búsqueda local y esquemas de aproximación; el problema del viajante (TSP) es la versión de optimización que busca el ciclo hamiltoniano más corto en un grafo ponderado y desempeña un papel central en logística y en el enrutamiento.

Historia y datos destacados

El término hamiltoniano deriva de William Rowan Hamilton, quien ideó el juego Icosian a mediados del siglo XIX: un rompecabezas que consiste en encontrar un ciclo hamiltoniano en el grafo de aristas del dodecaedro. Su enfoque algebraico, el Cálculo Icosiano, fue paralelo a otras innovaciones algebraicas de la época. Aunque Hamilton popularizó la idea, Thomas Kirkman ya había realizado trabajos anteriores sobre ciclos hamiltonianos en grafos poliédricos. Para una discusión histórica, véanse referencias al juego Icosian y al problema del dodecaedro (dodecaedro, Cálculo Icosiano).

Aplicaciones e importancia

Más allá de los rompecabezas recreativos, los caminos y ciclos hamiltonianos modelan rutas que deben visitar un conjunto de lugares exactamente una vez: planificación, rutas de vehículos, diseño de circuitos y ciertos diseños combinatorios. El problema del viajante es una derivación directa de optimización de las preguntas sobre ciclos hamiltonianos y ha impulsado una enorme cantidad de investigación en algoritmos, aproximaciones y teoría de la complejidad. Debido a que las versiones de decisión y de optimización son computacionalmente exigentes, el estudio de propiedades estructurales de los grafos que garanticen hamiltonicidad o permitan algoritmos eficientes sigue siendo un área activa de la combinatoria y la informática teórica.