Trayectorias y circuitos de Hamilton

Ahora se verá a la segunda categoría de problemas de gráficas, donde la tarea consiste en visitar cada vértice sólo una vez, con la excepción del vértice inicial, si éste también debe ser el último vértice. Por ejemplo, tal trayectoria podría ser útil para alguien que deba proporcionar servicio a un conjunto de máquinas expendedoras de manera regular. Se puede representar cada máquina expendedora mediante un vértice.

Una trayectoria hamiltoniana es aquella que contiene cada vértice sólo una vez. Un circuito hamiltoniano es aquel que contiene cada vértice sólo una vez, excepto el primer vértice, que también es el último. Este tipo de trayectoria recibe el nombre del matemático Sir William Hamilton, quien desarrolló y comercializó un juego que consistía en una gráfica de madera en forma de dodecaedro regular, con las instrucciones para encontrar lo que se llama circuito hamiltoniano. La figura (a) muestra una versión plana de este sólido, con un circuito hamiltoniano (uno de muchos) mostrado en la figura (b) mediante los vértices numerados en forma consecutiva.

Ejemplo 1.

Considere la gráfica de la figura a. La trayectoria a, b, c, d, e es una trayectoria hamiltoniana, pues contiene cada vértice sólo una vez. Sin embargo, no es difícil ver que no existe un circuito hamiltoniano para esta gráfica. Para la gráfica de la figura b, la trayectoria A, D, C, B, A (puede elegirse cualquier arista de B a A) es un circuito hamiltoniano. En las figuras c y d, no es posible tener una trayectoria hamiltoniana. (Verifique esta afirmación.)

Ejemplo 2.

Cualquier gráfica completa Kn tiene circuitos hamiltonianos. De hecho, si se parte de cualquier vértice, puede visitarse todos los demás en forma secuencial y en el orden deseado.

Pueden surgir preguntas sobre cuestiones análogas a las correspondientes a las trayectorias y circuitos de Euler acerca de las trayectorias y circuitos hamiltonianos. ¿Es posible determinar si existe una trayectoria o circuito de Hamilton? Si debe existir una trayectoria o circuito hamiltoniano ¿existe una manera eficiente de determinarlo?

Es claro que los bucles cerrados y las aristas múltiples no son muy útiles para determinar circuitos hamiltonianos, ya que no puede utilizarse los bucles cerrados, y sólo puede utilizarse una arista entre cualesquiera dos vértices. Así, se supondrá que cualquier gráfica mencionada no tiene bucles cerrados ni aristas múltiples.

Si una gráfica G de n vértices tiene un circuito hamiltoniano, entonces G debe tener al menos n aristas. Ahora, se establecerá algunas respuestas parciales, las cuales establecen que si una gráfica G tiene "suficientes" aristas, entonces puede determinarse un circuito hamiltoniano.

Sea G una gráfica conexa con n vértices, n> 2, sin bucles cerrados ni aristas múltiples. De nuevo, éstos son enunciados de existencia; no proporcionan métodos para construir un circuito hamiltoniano.

Teorema 1.

G tiene un circuito hamiltoniano si para cualesquiera dos vértices u y v de G que no sean adyacentes, el grado de u más el grado de v es mayor o igual que n.

Se omitirá la demostración de este resultado, pero mediante él puede demostrarse lo siguiente:

Corolario. G tiene un circuito hamiltoniano si cada vértice tiene grado mayor o igual que n/2.

Teorema 2.

Sea m el número de aristas de G. Entonces G tiene un circuito hamiltoniano si m ≥ ½(n²-3n+6). (Recuerde que n es el número de vértices.)

Ejercicios:

En los ejercicios del 1 al 6 determine si la gráfica dada tiene un circuito hamiltoniano, una trayectoria pero no un circuito hamiltoniano o ninguno de los dos. Si la gráfica tiene un circuito o una trayectoria indícalos.

En los ejercicios 7 al 10 determine un circuito hamiltoniano para cada gráfica.