Actualizado por ultima vez el 8 de enero de 2022, por Luis Benites.
Un dodecaedro (una figura sólida regular con doce caras pentagonales iguales) tiene un ciclo hamiltoniano.
Un ciclo hamiltoniano es un ciclo cerrado en un gráfico donde cada nodo (vértice) se visita exactamente una vez.
Un bucle es solo un borde que une un nodo consigo mismo; por lo tanto, un ciclo hamiltoniano es un camino que viaja desde un punto hacia sí mismo, visitando todos los nodos en el camino.
Si un grafo con más de un nodo (es decir, un grafo no singleton) tiene este tipo de ciclo, lo llamamos grafo hamiltoniano.
No existe ninguna ecuación o truco general para averiguar si un gráfico tiene un ciclo hamiltoniano; la única manera de determinar esto es hacer una búsqueda completa y exhaustiva, revisando todas las opciones.
Historia del ciclo hamiltoniano
El ciclo lleva el nombre de Sir William Rowan Hamilton quien, en 1857, inventó un juego de rompecabezas que consistía en buscar un ciclo hamiltoniano. El juego, llamado juego icosiano , se distribuía como un gráfico de dodecaedro con un agujero en cada vértice. Para resolver el rompecabezas o ganar el juego, había que usar clavijas y cuerdas para encontrar el ciclo hamiltoniano, un ciclo cerrado que visitaba cada hoyo exactamente una vez. La solución se muestra en la imagen de arriba.
Ejemplos de gráficos hamiltonianos
Todo grafo completo con más de dos vértices es un grafo hamiltoniano. Esto se deduce de la definición de un gráfico completo: un gráfico simple no dirigido tal que cada par de nodos está conectado por un borde único.
La gráfica de cada sólido platónico es una gráfica hamiltoniana. Entonces, la gráfica de un cubo, un tetraedro, un octaedro o un icosaedro son todas gráficas hamiltonianas con ciclos hamiltonianos.
Un gráfico con n vértices (donde n > 3) es hamiltoniano si la suma de los grados de cada par de vértices no adyacentes es n o mayor. Esto se conoce como el teorema de Ore .
Aplicaciones de los ciclos y gráficos hamiltonianos
La búsqueda de estos ciclos no es solo un juego divertido para la tarde libre. Tiene aplicaciones reales en campos tan diversos como gráficos por computadora, diseño de circuitos electrónicos, mapeo de genomas e investigación de operaciones.
Por ejemplo, al mapear genomas, los científicos deben combinar muchos fragmentos diminutos de código genético («lecturas», se les llama), en una sola secuencia genómica (una ‘supercadena’). Esto se puede hacer encontrando una ruta o ciclo hamiltoniano, donde cada una de las lecturas se considera nodos en un gráfico y cada superposición (lugar donde el final de una lectura coincide con el comienzo de otra) se considera un borde.
En una aplicación mucho menos compleja de exactamente las mismas matemáticas, los distritos escolares usan hamiltonianos para planificar la mejor ruta para recoger a los estudiantes de todo el distrito. Aquí los estudiantes pueden ser considerados nodos, los caminos entre ellos son bordes, y el autobús desea recorrer una ruta que pasará por cada casa de estudiantes exactamente una vez.
Referencias
Juego icosiano
sobre ciclos hamiltonianos y caminos hamiltonianos Algoritmos de gráficos de
ensamblaje del genoma
en bioinformática
