## 3.2.1 CICLOS HAMILTONIANOS

Se llama grafo G = (V, E) a toda estructura formada por un conjunto no vacío, V , cuyos elementos son llamados vértices o nodos, y un conjunto E de pares no ordenados de elementos de V , llamados aristas. Se suele representar un grafo mediante un diagrama de puntos y líneas en el que los primeros representan a los vértices y una línea entre los puntos vi y vj representa la arista (vi , vj ). Se llama camino a toda sucesión finita alterna de vértices y aristas, v1e1v2e2 . . . vn−1en−1vn, donde ei = (vi , vi+1), i = 1, 2, . . . , n − 1, en la que no se repite ningún vértice. En caso de que en la sucesión anterior los extremos v1 y vn coincidan y el resto de vértices sean distintos entre ellos y con v1 y vn , se le llama ciclo. Decimos que un ciclo es hamiltoniano si contiene a todos los vértices del grafo y, análogamente, un camino es hamiltoniano si pasa por todos los vértices del grafo. Un grafo se llama hamiltoniano si posee un ciclo hamiltoniano.

El análisis de los grafos hamiltonianos es, en términos generales, difícil, y aunque se conocen muchas condiciones necesarias, y otras muchas suficientes, no se conoce ninguna condición necesaria y suficiente aplicable a un grafo no dirigido cualquiera. Como un camino hamiltoniano es parte de un ciclo hamiltoniano nos encontramos con las mismas dificultades en el estudio de éstos. Dada la relación entre camino y grafo hamiltoniano (si en un ciclo hamiltoniano eliminamos una arista obtenemos un camino hamilltoniano), una forma de abordar el problema de los caminos hamiltonianos es reducirlo a uno de ciclos hamiltonianos. En este sentido un conocido teorema dice:

Teorema: Sea G = (V, E) un grafo no dirigido. Existe camino hamiltoniano en G si y sólo si G´ = (V´, E´ ) es hamiltoniano, siendo V´ = V U {a} y E´ = E U {(a, v) v ∈ V }. El estudio de la demostración de este teorema, inmediata por otra parte, nos permite extender el resultado. La representación gráfica resulta de gran ayuda. En la Figura se esboza el grafo G en el que se muestra el ciclo hamiltoniano.

###