Page 143 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Ciclo hamiltoniano (hamiltonian cycles)

INtroduccIóN

El problema de los puentes de Königsberg, también llamado más específicamente problema de
los siete puentes de Königsberg, es un célebre problema matemático, resuelto por Leonhard Eu-
ler en 1736 y cuya solución dio origen a la teoría de grafos. Su nombre se debe a Königsberg, ca-
pital de Prusia Oriental hasta 1945, cuando fue tomada por los soviéticos, los cuales la renombraron
como Kaliningrado.

Esta ciudad es atravesada por el río Pregel (en ruso Pregolya), el cual se bifurca para rodear con sus
brazos a la isla Kneiphof, dividiendo el terreno en cuatro regiones distintas, las que entonces estaban
unidas mediante siete puentes llamados puente del herrero, puente conector, puente verde, puente
del mercado, puente de madera, puente alto y puente de la miel. El problema fue formulado en el
siglo XVIII y consistía en encontrar un recorrido para cruzar a pie toda la ciudad pasando solo una
vez por cada uno de los puentes y regresando al mismo punto de inicio. El problema, formulado
originalmente de manera informal, consistía en responder la siguiente pregunta:
Dado el mapa de Königsberg, con el río Pregel dividiendo el plano en cuatro regiones
distintas, que están unidas a través de los siete puentes, ¿es posible dar un paseo
comenzando desde cualquiera de estas regiones, pasando por todos los puentes, reco-
rriendo solo una vez cada uno, y regresando al mismo punto de partida?

La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede
resolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos
existentes. Sin embargo, Euler en 1736, en su publicación Solutio problematis ad geometriam situs
pertinentis, demostró una solución generalizada del problema, que puede aplicarse a cualquier te-
rritorio en que ciertos accesos estén restringidos a ciertas conexiones, tales como los puentes de
Königsberg.

Para dicha demostración, Euler recurrió a una abstracción del mapa, enfocándose exclusivamente
en las regiones terrestres y en las conexiones entre ellas. Cada puente lo representó mediante una lí-
nea que unía a dos puntos, cada uno de los cuales representaba una región diferente. De este modo
el problema se reduce a decidir si existe o no un camino que comience por uno de los puntos azules
(figura 6.6), transitando por todas las líneas una única vez y regresando al mismo punto de partida.

137