Introducción

Una vez estudiados los conceptos fundamentales de la Teoría de grafos en el tema anterior, y entre ellos los de camino y ciclo, en este segundo y último tema de este módulo vamos a estudiar los ciclos o circuitos y los caminos de Euler y de Hamilton.

En el caso de Euler, el asunto surge a partir del famoso problema de los puentes de la ciudad de Könisberg. Este problema se considera, por muchos, el origen de la Teoría de los grafos.

Königsberg (actualmente Kaliningrado, Rusia) era una ciudad de Prusia del siglo XVIII. El problema tiene como protagonista al río Pregel, que atravesaba la ciudad, a dos islas que se encontraban en el mismo y a siete puentes que comunicaban las dos partes de la ciudad con las mismas. El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida.

Fue resuelto por Leonhard Euler. La idea genial de Euler fue representar la ciudad de Königsberg como un grafo en el que las cuatro partes de aquélla eran los vértices y los siete puentes eran las aristas.

Los circuitos de Hamilton son llamados así en honor a Sir William Rowan Hamilton, quien patentó un juego con la forma de un dodecaedro. Cada esquina del dodecaedro representa una ciudad. Trata de viajar a todas las ciudades pasando sólo una vez por cada una y volver al punto de partida.

Dedicaremos el tema al estudio de estos dos casos, además de ver al final, el algoritmo de Dijkstra para calcular la distancia más corta entre dos vértices.