Camino
Nodos explorados
Ciclo hamiltoniano
Camino hamiltoniano

Modo

    Objetivo

    Más sobre caminos y ciclos hamiltonianos

    Explorador de caminos hamiltonianos

    En 1857 William Rowan Hamilton inventó un rompecabezas: recorrer las aristas de un dodecaedro pasando por cada una de sus 20 esquinas exactamente una vez y terminar donde empezaste. Una ruta así se llama hoy ciclo hamiltoniano. Es fácil de comprobar y, en general, difícil de encontrar. Traza una tú mismo en el dodecaedro de Hamilton, en un tablero de ajedrez o en un grafo que dibujes, o mira cómo una búsqueda con retroceso la persigue, cuenta los callejones sin salida en los que cae y comprueba cuánto acortan la búsqueda unas pocas comprobaciones sencillas. Elige un grafo y un objetivo: un ciclo que vuelve a su inicio, o un camino. Trazar: haz clic en un vértice para empezar y luego en un vecino cada vez; los anillos discontinuos muestran adónde puedes ir. Un clic en el último vértice, Atrás o Deshacer retrocede un paso, y Pista indica un paso siguiente que todavía puede terminarse. Búsqueda: con Iniciar o Paso corre una búsqueda con retroceso, que añade vértices hasta atascarse y entonces vuelve atrás; los trazos rojos muestran los retrocesos y las barras cuentan los nodos por longitud de camino. Antes de empezar, un clic en un vértice elige dónde comienza. Las casillas activan y desactivan la poda, Comparar ejecuta la misma búsqueda con y sin ella, y Contar todos cuenta cada ciclo o camino de un grafo pequeño. Editar: haz clic para añadir un vértice, haz clic en dos vértices para unirlos o separarlos, arrastra para mover uno, y Eliminar quita el vértice seleccionado.

    Cómo funciona

    1. Elige un grafo, como el dodecaedro de Hamilton, el grafo de Petersen o un recorrido del caballo, o dibuja el tuyo en Editar, y elige como objetivo un ciclo o un camino.
    2. En Trazar, haz clic en un vértice para empezar y luego en un vecino tras otro. Atrás y Deshacer retroceden un paso, y Pista muestra un paso siguiente que todavía puede terminarse.
    3. En Búsqueda, pulsa Iniciar o Paso para ver cómo el retroceso busca una ruta, activa y desactiva la poda, y pulsa Comparar para ver cuántos nodos necesita cada versión.

    Hamilton frente a Euler

    Un camino euleriano usa cada arista una vez; un camino hamiltoniano pasa por cada vértice una vez. Suenan parecidos pero se comportan de forma muy distinta. Si un grafo conexo tiene un camino euleriano se decide contando los vértices de grado impar, como mostró Euler en 1736: lo tiene cuando no hay ninguno o hay dos. Para los caminos hamiltonianos no se conoce una regla así. Decidir si un grafo tiene un ciclo hamiltoniano es NP-completo, uno de los 21 problemas de la lista de Richard Karp de 1972, de modo que un método rápido para él daría métodos rápidos para miles de otros problemas difíciles. Lo que existe son condiciones que deciden algunos grafos. El teorema de Dirac de 1952 garantiza un ciclo hamiltoniano cuando cada vértice tiene grado al menos n/2, y el de Ore de 1960 cuando dos vértices no unidos tienen siempre grados que suman al menos n; un vértice de grado 1, un vértice de corte o dos clases de color de tamaños distintos lo descartan.

    Cómo funciona la búsqueda

    El retroceso construye el camino un vértice cada vez y, cuando se atasca, retira el último paso y prueba el siguiente vecino. Siempre encuentra un ciclo hamiltoniano si lo hay, pero el número de caminos parciales puede crecer exponencialmente. En la cuadrícula 5 × 5, que no tiene ciclo hamiltoniano, el retroceso simple explora 153.745 nodos antes de estar seguro. Dos comprobaciones detienen pronto los caminos sin esperanza: un vértice no visitado con menos de dos vecinos libres ya no puede encajar en un ciclo, y cuando los vértices no visitados se separan en partes distintas, ningún camino único puede cubrirlos. Con ambas, la misma demostración tarda 1.761 nodos. La regla de Warnsdorff de 1823, que prueba primero el vecino con menos movimientos siguientes, encuentra un recorrido del caballo en 8 × 8 desde una esquina en 64 movimientos sin un solo callejón sin salida.

    Preguntas frecuentes

    ¿Cuál es la diferencia entre un camino hamiltoniano y un ciclo hamiltoniano?

    Un camino hamiltoniano pasa por cada vértice de un grafo exactamente una vez. Un ciclo hamiltoniano hace lo mismo y luego vuelve por una arista más al punto de partida, así que puede empezar en cualquiera de sus vértices. Todo grafo con un ciclo hamiltoniano tiene un camino hamiltoniano (quita una arista del ciclo), pero no al revés: el grafo de Petersen tiene caminos hamiltonianos y ningún ciclo hamiltoniano.

    ¿Tiene el dodecaedro un ciclo hamiltoniano?

    Sí, 30, contando cada ciclo una vez sea cual sea su inicio y su sentido. Hamilton lo convirtió en el juego icosiano en 1857, un tablero con las 20 esquinas de un dodecaedro aplanado marcadas con consonantes, y vendió los derechos por 25 libras al fabricante de juguetes londinense John Jaques and Son. Contar todos encuentra los 30 ciclos en unos 1.400 nodos.

    ¿Por qué una cuadrícula 5 × 5 no tiene ciclo hamiltoniano?

    Colorea los 25 puntos como un tablero de ajedrez: 13 reciben un color y 12 el otro, y cada paso va al otro color. Un ciclo alterna colores en toda la vuelta, así que necesita tantos de uno como del otro, lo que 13 y 12 no dan. El mismo argumento vale para toda cuadrícula con un número impar de puntos, para un caballo en un tablero 5 × 5 o 7 × 7 (el caballo siempre cambia de color de casilla) y para el grafo de Herschel, cuyas dos clases tienen 6 y 5 vértices. Un camino hamiltoniano sigue siendo posible: empieza y termina en el color más numeroso.

    ¿Cómo encuentra la regla de Warnsdorff un recorrido del caballo?

    H. C. von Warnsdorff propuso en 1823 mover siempre el caballo a la casilla desde la que tendrá menos movimientos siguientes. Las casillas cercanas a los bordes y las esquinas, fáciles de aislar, se visitan así pronto, mientras el caballo todavía puede entrar en ellas. La regla es una regla práctica, no una garantía, y los empates hay que romperlos de algún modo, pero en un tablero 8 × 8 suele completar un recorrido sin volver atrás. Unida al retroceso, como en la aplicación, encuentra recorridos abiertos desde 5 × 5 y recorridos cerrados en los tableros 6 × 6 y 8 × 8.

    ¿Cuántos ciclos hamiltonianos tiene un grafo completo?

    (n − 1)!/2 para n ≥ 3. Fija el vértice de partida; los otros n − 1 pueden seguir en cualquier orden, y cada ciclo se cuenta dos veces, una por sentido. K₆ tiene 5!/2 = 60 y K₁₀ tiene 181.440. Son los viajes de ida y vuelta entre los que debe elegir un viajante de comercio, y por eso probarlos todos deja de ser posible tan pronto.

    ¿Listo para probarlo?

    Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

    Ir al editor