Camino hamiltoniano

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.

Un ciclo hamiltoniano en el grafo de un dodecaedro. El grafo del dodecaedro es hamiltoniano como el resto de grafos de sólidos platónicos

El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo^[1]​ 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 una sola vez. Se trata, en consecuencia, de encontrar un camino hamiltoniano en un grafo cuyos vértices son los escaques de un arcidriche de manera que dos vértices son adyacentes si y sólo si se puede pasar de uno a otro mediante un movimiento de caballo.

Definición

1. Un camino sin vértices repetidos que recorre todos los vértices del grafo se llama camino hamiltoniano.
2. Un camino hamiltoniano que sea un circuito se llama circuito hamiltoniano.
3. Un grafo que tiene un circuito hamiltoniano se llama grafo hamiltoniano.

Para grafos dirigidos, o dígrafos, las definiciones correspondientes tienen en cuenta que las aristas están dirigidas.

1. Un camino dirigido en un dígrafo es camino dirigido hamiltoniano si visita todos los vértices del dígrafo sin repetir ninguno.
2. Un ciclo dirigido hamiltoniano en un dígrafo es un camino dirigido hamiltoniano que es ciclo.
3. El grafo dirigido es dígrafo hamiltoniano si contiene un ciclo dirigido hamiltoniano.

Al contrario que en el caso de los grafos eulerianos, no se conoce ninguna caracterización de los grafos hamiltonianos. Desde luego, todos los grafos hamiltonianos son conexos pero no todos los grafos conexos son hamiltonianos.

Ejemplos

• Todos los grafos ciclos son hamiltonianos.
• Los grafos completos con más de dos vértices son hamiltonianos.
• Todos los campeonatos poseen caminos dirigidos hamiltonianos.^[2]​ Se puede consultar la demostración en [Theorem 2.2.1^[3]​].
• Todos los sólidos platónicos (el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro), considerados como grafos, son hamiltonianos.^[4]​
• Entre los grafos eulerianos los hay que son hamiltonianos y los hay que no lo son, y entre los grafos hamiltonianos los hay que son eulerianos y los hay que no lo son.
   

  Grafos: G₁, G₂, G₃ y G₄
  1. El grafo G₁ es euleriano y hamiltoniano.
  2. El grafo G₂ es euleriano y no es hamiltoniano.
  3. El grafo G₃ no es euleriano y es hamiltoniano.
  4. El grafo G₄ conexo, no es euleriano y no es hamiltoniano.

Condiciones necesarias

Podemos, no obstante, anotar algunas condiciones necesarias para que un grafo sea hamiltoniano.

• Un grafo hamiltoniano ha de ser conexo.
• Un grafo hamiltoniano no puede tener vértices de grado 1: en todos los vértices deben incidir al menos dos aristas, la de “entrada” y la de “salida”.
• Si S es un subconjunto del conjunto de vértices de un grafo G, escribimos G − S para designar el subgrafo que aparece al eliminar todos los vértices de S y todas las aristas adyacentes a los vértices de S.

Teorema.

Si un grafo G es hamiltoniano entonces para cualquier subconjunto no vacío de vértices S de G, el número de componentes conexas del subgrafo G − S es menor o igual que el cardinal de S.(Cf. [Theorem 6.2.4^[3]​])

En particular, un grafo hamiltoniano no puede poseer vértices de corte, esto es, un vértice tal que si lo eliminamos junto a todas las aristas que confluyen en él, el subgrafo resultante tiene más componentes conexas que el grafo original.

El recíproco no es cierto.

Condiciones suficientes

Teorema de Bondy-Chvátal

Existen muchos resultados que proporcionan condiciones suficientes que garanticen el carácter hamiltoniano de un grafo. De entrada, para poder analizar si un grafo de más de 2 vértices es hamiltoniano podemos suprimir los lazos y las aristas paralelas. Además un grafo con 2 vértices es hamiltoniano si y sólo si tiene al menos dos aristas entre ambos vértices. Por tanto nos concentramos en el análisis de grafos simples, sin lazos y con más de 2 vértices. La mejor aportación en este sentido es un teorema publicado en 1976 debido a J. A. Bondy y a V. Chvátal, que generaliza los resultados anteriormente encontrados por G. A. Dirac (1952) y Ø. Ore (1960). Todos estos resultados afirman, básicamente, que un grafo es hamiltoniano si existen “suficientes aristas”. Para enunciar el Teorema de Bondy-Chvátal es menester definir primero qué es la clausura de un grafo.

Definición. Dado un grafo G con n vértices, la clausura de G es el grafo que tiene los mismos vértices que G y que aparece al agregar todas las aristas de la forma {u, v} para cualquier par de vértices u y v que no sean adyacentes y cumplan que grado(v) + grado(u) ≥ n.

Teorema.

Un grafo es hamiltoniano si y sólo si lo es su clausura.^[5]​

Puede consultarse una demostración del Teorema de Bondy-Chvátal en [Theorem 7.20^[6]​].

Los teoremas de Ore y Dirac

Como todos los grafos completos son hamiltonianos, todos los grafos cuya clausura sea un grafo completo son hamiltonianos. Esto nos permite deducir algunas condiciones suficientes para que un grafo sea hamiltoniano; en particular aparece el Teorema de Ore y el Teorema de Dirac.

Teorema.

Si G es un grafo conexo, simple y sin lazos con n vértices, con n ≥ 3, en el cual grado(u) + grado(v) ≥ n para todo par de vértices no adyacentes u, v, entonces G es hamiltoniano.^[7]​

Se puede consultar una demostración directa del Teorema de Ore en [Theorem 6.2.5^[3]​].

Teorema.

Si G es un grafo conexo, simple, sin lazos y con n vértices en el cual grado(u) ≥ n/2 para todo vértice u, entonces G es hamiltoniano.^[8]​

Corolario. Si G es un grafo conexo, simple y sin lazos con n vértices, con n ≥ 3, en el cual grado(u) + grado(v) ≥ n − 1 para todo par de vértices no adyacentes u, v, entonces G posee un camino hamiltoniano.

Ejemplo. Consideremos el siguiente grafo, al que se suele denominar como “grafo casa”, que es claramente hamiltoniano:

 

Grafo casa

• No podemos deducir que es hamiltoniano aplicando el Teorema de Dirac pues hay vértices de grado 2 y 2 < 5/2.
• No podemos deducir que es hamiltoniano aplicando el Teorema de Ore pues hay dos pares de vértices no adyacentes de grado 2 y 2 + 2 < 5.
• La clausura del grafo casa se obtiene añadiendo en primer lugar las aristas rojas y después las azules. Por lo tanto, la clausura del grafo es el grafo completo de 5 vértices. El grafo completo es hamiltoniano. En consecuencia se puede deducir que el grafo casa es hamiltoniano aplicando el Teorema de Bondy-Chvátal.

 

Clausura del grafo casa

Una consecuencia del Teorema de Ore es el resultado siguiente. Su demostración puede consultarse en [Theorem 6.2.14^[3]​].

Corolario. Si G es un grafo conexo, simple y sin lazos con n vértices, con n ≥ 3, en el cual grado(u) + grado(v) ≥ n − 1 para todo par de vértices no adyacentes u, v, entonces G posee un camino hamiltoniano.

Ejemplo. Si G es un grafo simple, sin lazos y con n vértices en el cual grado(u) + grado(v) ≥ n − 1 para todo par de vértices u, v, entonces G no es necesariamente hamiltoniano. Esto se aprecia en muchos ejemplos; en particular, en los siguientes.

 

Ejemplos

Dígrafos hamiltonianos

Para grafos dirigidos mencionemos un resultado de H. Meyniel que proporciona también una condición suficiente para que un dígrafo fuertemente conexo sea hamiltoniano.

Teorema.

Si D es un grafo dirigido fuertemente conexo de n vértices en el cual grado(u) + grado(v) ≥ 2n − 1 para toda pareja u, v de vértices no adyacentes entonces D es grafo dirigido hamiltoniano.^[9]​

Referencias

1. Michael R. Garey y David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
2. L. Rédei, Eine kombinatorischer Satz. Acta. Litt. Sci. Szeged 7 (1934), 39–43.
3. R. Balakrishnan y K. Ranganathan. A textbook of Graph Theory. Springer, Nueva York, Berlín, Heidelberg, 2000.
4. M. Gardner, Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi. Sci. Amer. 196, 150– 156, May 1957.
5. J. A. Bondy y V. Chvátal, A method in graph theory. Discrete Math. 15 (1976) 111-135.
6. A. D. Polimeni, H. J. Straight, Foundations of Discrete Mathematics. Brooks/Cole, Pacific Grove 1985.
7. O. Ore, Note on Hamilton circuits. Amer. Math. Monthly 67 (1960) 55.
8. G. A. Dirac, Some theorems on abstract graphs. Proc. London Math. Soc, 2 (1952) 69-81
9. H. Meyniel, Une condition sufisante d’existence d’un graphe orienté. J. Combinatorial Theory B 14 (1973), 137–147.

•   Datos: Q273037
•   Multimedia: Hamiltonian paths