Camino 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

Un camino hamiltoniano, en el campo matemático de la teoría de grafos, es un camino de un grafo, 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.

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 digrafos, las definiciones correspondientes tienen en cuenta que las aristas están dirigidas.

  1. Un camino dirigido en un digrafo es camino dirigido hamiltoniano si visita todos los vértices del digrafo sin repetir ninguno.
  2. Un ciclo dirigido hamiltoniano en un digrafo es un camino dirigido hamiltoniano que es ciclo.
  3. El grafo dirigido es digrafo 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.

Other Languages