CIRCUITO DE HAMILTON

En 1856, el matemático William Hamilton presentó al mundo un puzzle (juego de mesa). El juego estaba en un dodecaedro regular cuyos 20 vértices se marcaban cada uno con el nombre de una ciudad importante en aquella época. El juego consistía en salir de una determinada ciudad y encontrar una ruta que permitiera para por todas las demás ciudades una sola vez y regresar al punto de partida. El dodecaedro era tan incómodo de manipular que Hamilton desarrollo una versión del juego en que lo reemplazaba por un grafo con 20 vértices unidos mediante 30 aristas. El grafo resultante se conoce como grafo del dodecaedro.

W. R. Hamilton (1805 – 18659) inventó (y patentó) un juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro.

Se denomina camino Hamiltoniano en un grafo con aristas no orientados G = (V, A) a cualquier camino simple que contenga a todos los vértices de G pasando una sola vez por cada uno de ellos, pero permitiendo que el vértice final. Si el camino Hamiltaniano es cerrado, se le denomina circuito Hamiltoniano.

Se dice que un grafo es de Hamilton si existe un ciclo que recorre todos sus vértices y se lo denomina ciclo Hamiltoniano.

A pesar de la preocupación y el estudio de las matemáticos, no existe hoy en día u teorema que permita determinar si un grafo es Hamiltoniano o no. El método de ensayo y error es la única forma posible de encontrar una respuesta al problema.

CICLO HAMILTON: Es un ciclo simple que contiene todos los vértices de G.

Un ciclo Hamiltoniano es una trayectoria que empieza y termina  en el mismo.

REFERENCIAS:

Lopez, A. (19 de Mayo de 2016). Circuito de Hamilton. Obtenido de SlideShare.net: http://es.slideshare.net/AntonellaLopez7/circuito-de-hamilton