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.
El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo 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.
Para grafos dirigidos, o dígrafos, las definiciones correspondientes tienen en cuenta que las aristas están dirigidas.
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.
Podemos, no obstante, anotar algunas condiciones necesarias para que un grafo sea hamiltoniano.
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])
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.
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.
Puede consultarse una demostración del Teorema de Bondy-Chvátal en [Theorem 7.20].
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.
Se puede consultar una demostración directa del Teorema de Ore en [Theorem 6.2.5].
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.
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:
Una consecuencia del Teorema de Ore es el resultado siguiente. Su demostración puede consultarse en [Theorem 6.2.14].
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.
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.
Escribe un comentario o lo que quieras sobre Camino hamiltoniano (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)