Page 145 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Figura 6.8. Ejemplo de un ciclo hamiltoniano

Un ejemplo práctico se observa en la figura 6.9:

Figura 6.9. Ejemplo práctico de un ciclo hamiltoniano

Los caminos y ciclos hamiltonianos fueron nombrados después que su inventor lanzara un juguete
que involucraba encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Ha-
milton resolvió este problema usando cuaterniones (extensión de los números reales, similar a la de
los números complejos), aunque esta solución no se generaliza a todos los grafos.

En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino,
una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si, además,
el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano, aunque con una
observación: si un grafo no es conexo, no puede tener camino ni circuito Hamiltoniano.

139