Verificador de Camino Hamiltoniano

Verificador de Camino Hamiltoniano

El Verificador de Camino Hamiltoniano decide si un grafo contiene un camino hamiltoniano —una secuencia que visita cada vértice exactamente una vez— o un ciclo hamiltoniano, que además regresa al vértice inicial. Combina verificaciones estructurales rápidas (conectividad, prerrequisitos de grado, teorema de Dirac, teorema de Ore) con una búsqueda de backtracking ajustada mediante la heurística de Warnsdorff, y visualiza el camino testigo con una animación paso a paso.

¿Qué es un camino hamiltoniano?

Dado un grafo G = (V, E) con n vértices, un camino hamiltoniano es una secuencia ordenada v₁, v₂, …, v_n de todos los vértices tal que cada par consecutivo (v_i, v_i+1) es una arista de G, y cada vértice aparece exactamente una vez. Si adicionalmente (v_n, v₁) es una arista, la secuencia es un ciclo hamiltoniano.

El problema lleva el nombre de William Rowan Hamilton, quien en 1857 inventó el juego icosiano, un rompecabezas que pedía al jugador encontrar un ciclo que visitara cada vértice de un dodecaedro regular exactamente una vez.

Por qué es difícil: NP-completitud

Tanto el problema de decisión del camino hamiltoniano como el del ciclo hamiltoniano son NP-completos (Karp, 1972). A menos que P = NP, no existe un algoritmo de tiempo polinomial que resuelva todas las instancias. En el peor de los casos, el backtracking explora un árbol de búsqueda de tamaño hasta (n−1)! para un ciclo. Por esta razón, la calculadora limita la entrada a 20 vértices; un pequeño aumento polinomial en n produce un aumento explosivo en el tiempo de ejecución.

En la práctica, la heurística de Warnsdorff (originalmente ideada por Heinrich Warnsdorff en 1823 para el recorrido del caballo) hace que la búsqueda sea drásticamente más rápida en grafos estructurados: en cada paso, el algoritmo extiende el camino actual al vecino no visitado con el número más pequeño de vecinos restantes no visitados. Esta regla codiciosa evita que la búsqueda se bloquee en un callejón sin salida y a menudo encuentra un recorrido hamiltoniano con cero retrocesos en grafos con buen comportamiento.

Condiciones necesarias: rechazo rápido

Antes de ejecutar una búsqueda costosa, la calculadora rechaza grafos que no pueden contener un camino hamiltoniano:

• Conectividad. Un camino hamiltoniano debe visitar cada vértice, por lo que el grafo debe tener exactamente una componente conectada. Para grafos dirigidos, se requiere conectividad débil (ignorando la dirección de las flechas).
• Grado (no dirigido). Como máximo dos vértices pueden tener grado 1; esos son los únicos candidatos para los extremos del camino. Para un ciclo hamiltoniano, cada vértice debe tener un grado de al menos 2.
• Grado (dirigido). Para un camino hamiltoniano, como máximo un vértice puede tener un grado de entrada 0 (el inicio) y como máximo uno puede tener un grado de salida 0 (el final). Para un ciclo hamiltoniano, cada vértice debe tener tanto un grado de entrada ≥ 1 como un grado de salida ≥ 1.

Estas reglas rechazan muchas entradas imposibles en tiempo lineal, evitando el esfuerzo desperdiciado en el backtracking.

Condiciones suficientes: teoremas clásicos

Varios teoremas clásicos proporcionan condiciones suficientes (pero no necesarias) que garantizan un ciclo hamiltoniano en grafos simples no dirigidos. Si alguno de estos se aplica, la calculadora marca el resultado como "GARANTIZA" sin siquiera ejecutar la búsqueda, aunque sigue mostrando un ciclo testigo.

Teorema de Dirac (1952)

Si G es un grafo simple no dirigido de n ≥ 3 vértices y cada vértice tiene un grado de al menos n / 2, entonces G tiene un ciclo hamiltoniano.

Teorema de Ore (1960)

Si para cada par de vértices no adyacentes u y v tenemos deg(u) + deg(v) ≥ n, entonces G tiene un ciclo hamiltoniano. La condición de Ore es estrictamente más débil que la de Dirac, por lo que Ore implica Dirac.

El fallo de la condición de Dirac o de Ore no significa que el grafo carezca de un ciclo hamiltoniano; muchos grafos no satisfacen ninguna de las dos pero contienen uno (por ejemplo, un ciclo simple de n vértices tiene un grado mínimo de 2, muy por debajo de n/2 para un n grande).

El algoritmo de búsqueda interno

Cuando las verificaciones previas no resuelven la cuestión, la calculadora ejecuta una búsqueda de backtracking sobre la representación de adyacencia del grafo. Tácticas clave:

1. Bitmask de conjunto visitado. Los vértices visitados se almacenan como un bitmask (prueba rápida de membresía O(1) para hasta 20 vértices).
2. Heurística de Warnsdorff. En cada extensión, los vecinos se prueban en orden de su grado no visitado restante (el más pequeño primero), imitando un orden de "baja ramificación".
3. Selección de raíz. Para el ciclo hamiltoniano, solo se necesita un vértice inicial (los ciclos son invariantes ante la rotación). Para el camino hamiltoniano, los inicios se prueban en orden ascendente de grado de salida, las posiciones más raras primero.
4. Presupuesto de pasos. Un límite estricto evita que las instancias patológicas se ejecuten indefinidamente; la interfaz informa el veredicto como "tiempo agotado" si se agota el presupuesto.

Hamiltoniano vs. Euleriano

Es fácil confundir los problemas hamiltonianos y eulerianos; suenan similares pero son fundamentalmente diferentes:

Formatos de entrada compatibles

Lista de aristas

Una arista por línea, o separadas por comas. Separadores admitidos: A-B, A B, A,B, A--B, A->B, A<-B. Use -> para forzar una interpretación dirigida.

Matriz de adyacencia

Matriz cuadrada de valores 0/1, una fila por línea, separada por espacios o comas. Proporcione etiquetas opcionales en el campo Etiquetas de matriz; de lo contrario, se usarán A, B, C… automáticamente.

Cómo usar este verificador

1. Elija un formato de entrada: Lista de aristas para grafos pequeños escritos a mano, Matriz de adyacencia para pegados desde código o libros de texto.
2. Pegue su grafo en el área de texto. Para la entrada de matriz, opcionalmente proporcione etiquetas de vértices.
3. Elija qué verificar: Solo camino, Solo ciclo, o Ambos en una sola ejecución.
4. Seleccione el tipo de grafo: La detección automática infiere si es dirigido a partir del estilo de flecha (->) o la simetría de la matriz.
5. Haga clic en Verificar hamiltoniano. La página de resultados muestra un encabezado con el veredicto, la verificación previa de condiciones necesarias, las pruebas de condiciones suficientes de Dirac / Ore, el camino testigo (si existe) y una visualización interactiva.
6. Reproduzca el testigo usando los controles de Reproducir / Paso. Observe cómo el camino se ilumina arista por arista en el grafo.

Ejemplo práctico: El grafo de Petersen

El famoso grafo de Petersen (10 vértices, 15 aristas, 3-regular) es un ejemplo de libro de texto de un grafo con un camino hamiltoniano pero sin ciclo hamiltoniano. Pegue esto en el campo de lista de aristas y haga clic en Verificar:

El verificador confirma: se encontró un camino hamiltoniano (por ejemplo, 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), pero la búsqueda exhaustiva no encuentra forma de cerrar el bucle de regreso al inicio, un resultado demostrado por primera vez en la década de 1890.

Aplicaciones comunes

• Enrutamiento y el problema del vendedor viajero (TSP): cada recorrido del TSP es un ciclo hamiltoniano en el grafo completo ponderado.
• Ensamblaje del genoma: la reconstrucción de una secuencia de ADN a partir de lecturas superpuestas puede modelarse como un camino hamiltoniano en un grafo de superposición.
• Diseño de circuitos: ordenar los pines en una PCB para un cableado de longitud mínima.
• IA de juegos y resolución de acertijos: recorridos del caballo en un tablero de ajedrez, juego icosiano.
• Programación de tareas (scheduling): secuenciar tareas de modo que cada una transite de manera factible a la siguiente.
• Enseñanza de la combinatoria: ilustrar la NP-completitud con pequeños ejemplos que se pueden resolver a mano.

Preguntas frecuentes

¿Qué es un camino hamiltoniano?

Un camino hamiltoniano es un recorrido a través de un grafo que visita cada vértice exactamente una vez. Lleva el nombre de William Rowan Hamilton, quien estudió el problema en el grafo del dodecaedro en 1857. Decidir si tal camino existe es un problema NP-completo, por lo que ningún algoritmo conocido lo resuelve en tiempo polinomial para todos los grafos.

¿En qué se diferencia un ciclo hamiltoniano de un camino hamiltoniano?

Un ciclo hamiltoniano es un camino hamiltoniano que regresa a su vértice de inicio, formando un bucle cerrado que visita cada vértice exactamente una vez. Todo ciclo hamiltoniano contiene un camino hamiltoniano (solo hay que quitar la arista de cierre), pero lo inverso no es cierto: muchos grafos tienen un camino hamiltoniano pero no un ciclo hamiltoniano.

¿Qué dice el teorema de Dirac?

El teorema de Dirac (1952) establece que cualquier grafo simple no dirigido de n ≥ 3 vértices en el que cada vértice tiene un grado de al menos n/2 contiene un ciclo hamiltoniano. Es una condición suficiente pero no necesaria: muchos grafos que no alcanzan el umbral de Dirac todavía tienen ciclos hamiltonianos.

¿Qué dice el teorema de Ore?

El teorema de Ore (1960) establece que si, para cada par de vértices no adyacentes u y v en un grafo simple de n ≥ 3 vértices, la suma de sus grados es al menos n, entonces el grafo tiene un ciclo hamiltoniano. La condición de Ore es más débil que la de Dirac, por lo que el teorema de Ore se aplica siempre que se aplica el teorema de Dirac.

¿Por qué la búsqueda está limitada a 20 vértices?

Los problemas de decisión de camino y ciclo hamiltoniano son NP-completos. El tiempo de ejecución en el peor de los casos aumenta exponencialmente con el número de vértices. Con la poda y la heurística de Warnsdorff, la calculadora maneja rápidamente muchos grafos pequeños de hasta 20 vértices, pero las instancias más difíciles pueden agotar el tiempo. Más allá de los 20 vértices, se deben usar solvers especializados como Concorde o formulaciones de programación entera.

¿Qué es la heurística de Warnsdorff?

La regla de Warnsdorff, propuesta en 1823 para el problema del recorrido del caballo, dice que en cada paso se debe visitar el siguiente vértice que tenga el menor número de vecinos no visitados restantes. Esta regla de apariencia codiciosa poda drásticamente el árbol de backtracking en la práctica y, a menudo, encuentra caminos hamiltonianos sin retroceder en absoluto en grafos regulares.

¿Esta herramienta encuentra todos los caminos hamiltonianos?

No, encuentra un único camino o ciclo testigo cuando existe uno. Contar el número total de caminos hamiltonianos es en sí mismo un problema #P-completo y mucho más difícil que el problema de decisión. Para la enumeración, son más apropiadas las herramientas especializadas o los solvers de programación entera.

Lectura adicional

• Camino hamiltoniano — Wikipedia
• Problema del camino hamiltoniano — Wikipedia
• Teorema de Dirac sobre ciclos hamiltonianos — Wikipedia
• Teorema de Ore — Wikipedia
• Regla de Warnsdorff — Wikipedia

Operaciones matemáticas avanzadas:

• Calculadora de Matriz de Adyacencia Nuevo
• Calculadora de Antilogaritmo Popular
• Calculadora de funciones Beta
• Calculadora de Coeficientes Binomiales
• Calculadora de distribución binomial
• Calculadora Bit a Bit
• Simplificador de Álgebra Booleana Nuevo
• Calculadora del Teorema del Límite Central Popular
• Calculadora del Teorema Chino del Resto
• Calculadora de Combinación Popular
• Calculadora de Función de Error Complementaria
• Calculadora de Números Complejos Popular
• Calculadora de fracciones continuas
• Calculadora de Desarreglo (Subfactorial)
• Calculadora de Camino más Corto de Dijkstra
• Calculadora de Entropía
• Calculadora de función error
• Calculadora de la Función Totiente de Euler
• Calculadora de decaimiento exponencial
• Calculadora de Crecimiento Exponencial de Alta Precisión
• Calculadora de Integral Exponencial
• Calculadora de Exponentes (Alta Precisión)
• Calculadora del Algoritmo Euclidiano Extendido
• Calculadora de Factorial
• Calculadora de Función Gamma
• Calculadora de Proporción Áurea Popular
• Calculadora de Coloración de Grafos Nuevo
• Validador de secuencia de grados de grafo
• Calculadora de Orden en Teoría de Grupos Nuevo
• Calculadora de Media Vida
• Verificador de Camino Hamiltoniano Nuevo
• Calculadora de Inclusión-Exclusión Nuevo
• Solucionador de Mapa de Karnaugh (K-Map) Nuevo
• Solucionador de Programación Lineal Nuevo
• Calculadora de Estado Estacionario de Cadena de Markov
• Calculadora de Árbol de Expansión Mínimo
• Calculadora de Exponenciación Modular Nuevo
• Calculadora del Inverso Multiplicativo Modular
• Calculadora de Distribución Binomial Negativa Popular
• Calculadora de Flujo de Red (Flujo Máximo) Nuevo
• Calculadora de Tasa de Crecimiento Porcentual Popular
• Calculadora de Permutación Popular
• Calculadora de Permutaciones con Repetición Nuevo
• Calculadora del Principio del Palomar
• Verificador de Grafo Planar Nuevo
• Calculadora de Distribución de Poisson
• Calculadora de Raíces de Polinomios con Pasos Detallados
• Calculadora de Raíz Primitiva
• Calculadora de probabilidad
• Calculadora de Distribución de Probabilidad
• Calculadora de Proporciones
• Calculadora de Fórmula Cuadrática
• Calculadora de Anillos y Cuerpos Nuevo
• Calculadora de Redondeo Nuevo
• Calculadora Científica Popular
• Calculadora de notación científica Popular
• Calculadora de Teoría de Conjuntos
• Calculadora de Cifras Significativas Nuevo
• Solucionador del Problema del Matrimonio Estable Nuevo
• Calculadora de Números de Stirling
• Calculadora de Suma de Cubos
• Calculadora de suma de números enteros positivos
• Calculadora de Suma de Cuadrados
• Calculadora de Ordenación Topológica Nuevo
• Solucionador del Viajante de Comercio (TSP) Nuevo
• Generador de Tabla de Verdad
• Generador de Diagrama de Venn (3 Conjuntos)