Camino hamiltoniano

Carta Poco común · N.º 184969

En teoría de grafos, un camino hamiltoniano en un grafo es un camino (es decir, una sucesión de aristas adyacentes), que visita todos los vértices del grafo una sola vez. Si además el primer y último vértice visitado coincide, el camino es un ciclo hamiltoniano. El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo​ y como tal aparece en la lista de los 21 problemas NP-completos de Karp. El nombre proviene del matemático irlandés sir William Rowan Hamilton (1805-65), que propuso viajar a veinte ciudades del mundo, representadas como los vértices de un dodecaedro regular, siguiendo las aristas del dodecaedro. No obstante, los ciclos y caminos actualmente denominados hamiltonianos aparecieron mucho antes. Al parecer, ya en el siglo IX el poeta indio Rudrata nombra el llamado camino del caballo. Se trata de una sucesión de movimientos del caballo sobre un arcidriche de manera que esta pieza, el caballo, visite todos y cada uno de los escaques…

Leer en Wikipedia · Imagen Christoph Sommer, CC BY-SA 3.0