Caminos y ciclos hamiltonianos explicados
Dibuja cinco puntos en círculo, une cada uno con sus dos vecinos, y puedes dar la vuelta pasando una vez por cada punto y volver a casa: un ciclo hamiltoniano. Añade unas aristas o quita algunas y la pregunta se vuelve sorprendentemente difícil. Si un grafo tiene un ciclo así es uno de los problemas más conocidos que ningún ordenador sabe todavía responder rápido para todo grafo.
Cada vértice una vez
Un grafo es un conjunto de puntos, los vértices, unidos por líneas, las aristas. Un camino hamiltoniano va por aristas y pasa por cada vértice exactamente una vez; un ciclo hamiltoniano además vuelve adonde empezó, así que tiene tantas aristas como vértices. Un grafo con un ciclo hamiltoniano se llama hamiltoniano. Comprobar una ruta propuesta es fácil: cuenta los vértices y mira cada paso. Encontrar una, o demostrar que no hay ninguna, es la parte difícil, porque el número de órdenes en que podrían visitarse los vértices crece como n!, ya 2,4 × 10¹⁸ para 20 vértices.
El juego icosiano de Hamilton
William Rowan Hamilton, el matemático irlandés que descubrió los cuaterniones, inventó el juego icosiano en 1857. Su tablero mostraba un dodecaedro aplanado en el plano, con sus 20 esquinas marcadas con consonantes, y la tarea principal era poner clavijas numeradas del 1 al 20 en las esquinas de modo que los números consecutivos, y el 20 y el 1, estuvieran unidos por aristas. Hamilton vendió los derechos por 25 libras al fabricante de juguetes londinense John Jaques and Son, que lo sacó en 1859; se vendió mal. El rompecabezas tiene 30 soluciones, contando un ciclo una vez sea cual sea su inicio y su sentido. La pregunta en sí no era nueva: Thomas Kirkman había preguntado qué poliedros tienen un ciclo por todas sus esquinas en un artículo enviado a la Royal Society en 1855, y había mostrado uno que no lo tiene.
Recorridos del caballo
Un recorrido del caballo mueve un caballo de ajedrez de modo que caiga en cada casilla exactamente una vez: un camino hamiltoniano en el grafo cuyos vértices son las casillas y cuyas aristas son los movimientos del caballo. Un recorrido cerrado termina a un salto de caballo de su inicio, es decir, un ciclo hamiltoniano. Los ajedrecistas planteaban estos problemas hace más de mil años, y Euler los estudió en un artículo de 1759. En 1823 H. C. von Warnsdorff propuso ir siempre a la casilla con menos movimientos siguientes; esta regla sencilla suele completar un recorrido de un tablero 8 × 8 sin volver atrás. El caballo siempre cambia de color de casilla, así que un recorrido cerrado necesita tantas casillas claras como oscuras, lo que descarta los tableros con un número impar de casillas. Allen Schwenk mostró en 1991 exactamente qué tableros rectangulares tienen un recorrido cerrado; entre los cuadrados, todos los de lado par desde 6. El tablero de ajedrez corriente tiene 13.267.364.410.532 recorridos cerrados, contados por Brendan McKay en 1997.
Grafos sin ciclo hamiltoniano
Las demostraciones más rápidas de que no hay ciclo son argumentos de recuento. Si los vértices pueden colorearse con dos colores de modo que cada arista una colores distintos, un ciclo alterna y necesita tantos vértices de cada color; una cuadrícula 5 × 5 tiene 13 de uno y 12 del otro, así que no tiene ciclo hamiltoniano. Un vértice de corte, cuya eliminación parte el grafo, tendría que atravesarse dos veces, y un vértice de grado 1 no puede atravesarse en absoluto. Algunos grafos escapan a todos esos argumentos. El grafo de Petersen, publicado por Julius Petersen en 1898, tiene 10 vértices de grado 3 y ningún ciclo hamiltoniano, y sin embargo borrar cualquier vértice deja un grafo que sí lo tiene; es el grafo hipohamiltoniano más pequeño. El grafo de Herschel, llamado así por Alexander Stewart Herschel, que escribió sobre el juego icosiano en 1862, tiene 11 vértices y 18 aristas y es el grafo de un poliedro con nueve caras cuadrangulares. A ningún poliedro con menos esquinas le falta un ciclo hamiltoniano. En 1884 Peter Guthrie Tait conjeturó que todo poliedro con tres aristas en cada esquina tiene uno; W. T. Tutte encontró un contraejemplo con 46 vértices en 1946.
Condiciones que garantizan uno
Si un grafo tiene muchas aristas, un ciclo hamiltoniano es seguro. Gabriel Dirac demostró en 1952 que un grafo con n ≥ 3 vértices en el que cada vértice tiene grado al menos n/2 tiene uno, y Øystein Ore debilitó la condición en 1960: basta con que dos vértices no unidos tengan siempre grados que sumen al menos n. Ambas condiciones valen solo en un sentido. Un simple anillo de 100 vértices tiene grado 2 en todas partes, muy por debajo de 50, y aun así es un ciclo hamiltoniano. Ese es el panorama general: hay condiciones suficientes y hay razones de fracaso, y entre medias se extiende un gran territorio de grafos que solo una búsqueda puede decidir.
Por qué no se conoce una prueba rápida
Decidir si un grafo tiene un ciclo hamiltoniano es NP-completo; fue uno de los 21 problemas de la lista de Richard Karp de 1972. Un método que lo resolviera rápido para todo grafo resolvería rápido miles de otros problemas y zanjaría la cuestión P frente a NP. El contraste con los caminos eulerianos, que usan cada arista una vez, es llamativo: Euler mostró en 1736 que contar los vértices de grado impar zanja esa pregunta al instante. Los mejores métodos exactos para ciclos hamiltonianos siguen tardando tiempo exponencial. La programación dinámica sobre todos los subconjuntos de vértices, hallada por Richard Bellman y por Michael Held y Richard Karp en 1962, necesita unos n² × 2ⁿ pasos, y el método aleatorizado de Andreas Björklund de 2010 unos 1,657ⁿ. En la práctica el retroceso con buena poda maneja grafos de unas pocas docenas de vértices, y el problema del viajante, que busca el ciclo hamiltoniano más corto, es la versión con pesos de la misma pregunta.
Códigos Gray y el hipercubo
Escribe los números del 0 al 7 como códigos de 3 bits y une dos códigos cuando difieren exactamente en un bit: el resultado es el grafo de un cubo. Un ciclo hamiltoniano que lo recorre, por ejemplo 000, 001, 011, 010, 110, 111, 101, 100, enumera los ocho códigos de modo que cada uno difiere del anterior en un solo bit. Una lista así es un código Gray, llamado por Frank Gray de los Bell Labs, que lo describió en una patente presentada en 1947. Todo hipercubo tiene uno: escribe los códigos con un bit menos, luego la misma lista al revés, y pon un 0 delante de la primera mitad y un 1 delante de la segunda. Los codificadores rotatorios usan códigos Gray para que una lectura tomada entre dos posiciones nunca se equivoque en más de un paso. El cubo tiene 6 ciclos hamiltonianos y el hipercubo de 4 bits tiene 1.344.
Explóralo
Abre el explorador de caminos hamiltonianos para probar tú mismo el rompecabezas de Hamilton, con anillos discontinuos que muestran adónde puedes ir, o cambia a Búsqueda y mira trabajar al retroceso: el camino crece, los trazos rojos marcan dónde vuelve atrás, y las barras cuentan los nodos por longitud de camino. Activa y desactiva la comprobación de callejones, la de conexión y el orden de Warnsdorff, compara cuántos nodos necesita cada una, cuenta todos los ciclos de un grafo pequeño, o dibuja tu propio grafo y mira cuáles de las pruebas rápidas se aplican.
Preguntas frecuentes
¿Un grafo con un circuito euleriano es también hamiltoniano, o al revés?
Ninguno se sigue del otro. La pajarita, dos triángulos que comparten un vértice, tiene un circuito euleriano porque todos los grados son pares, pero ningún ciclo hamiltoniano, ya que el vértice compartido tendría que atravesarse dos veces. El grafo completo K₄ tiene ciclos hamiltonianos, pero sus cuatro vértices tienen grado 3, así que no tiene circuito euleriano.
¿No puede un ordenador probar simplemente todos los órdenes?
Solo en grafos pequeños. Hay n! órdenes de n vértices, unos 2,4 × 10¹⁸ para 20. El retroceso lo hace mucho mejor, porque solo sigue aristas y abandona un camino parcial en cuanto se atasca: encuentra los 30 ciclos del dodecaedro de 20 vértices en unos 1.400 pasos. Pero en algunos grafos el número de caminos parciales crece igualmente de forma exponencial, y no se conoce ningún método que lo evite para todo grafo.
¿Es el problema del camino hamiltoniano más fácil que el del ciclo?
No, ambos son NP-completos. Cada uno se reduce al otro: añade un vértice nuevo unido a todos los viejos, y el grafo viejo tiene un camino hamiltoniano exactamente cuando el nuevo tiene un ciclo hamiltoniano. En el otro sentido, un problema de ciclo pasa a ser de camino añadiendo una copia de un vértice, con los mismos vecinos, y un vértice final nuevo unido al vértice y otro a su copia.
¿Por qué un recorrido del caballo en un tablero 5 × 5 tiene que empezar en el color de las esquinas?
De las 25 casillas, 13 tienen el color de las esquinas y 12 el otro, y el caballo cambia de color en cada movimiento. Un recorrido de 25 casillas alterna colores, así que empieza y termina en el color que tiene más casillas. La aplicación encuentra los 1.728 recorridos abiertos del tablero 5 × 5, 864 si un recorrido y su inverso cuentan como uno, y todos empiezan y terminan en una casilla del color de las esquinas.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Abrir el explorador de caminos hamiltonianos