sábado, 26 de julio de 2008

Revisando los siete puentes de Königsberg con Google Maps

El conocido problema de Los siete puentes de Königsberg (en la actualidad Kaliningrado) consiste en:
Dos islas en el río Pregel que cruza Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando todos los puentes una sola vez?
El problema fue resuelto en 1736 por Leonhard Euler, demostrando que no era posible encontrar tal camino, y dando origen a la Teoría de Grafos.

La situación es algo distinta en la actualidad, ya que de todos los puentes destruidos durante la Segunda Guerra Mundial, solo algunos fueron posteriormente reconstruidos. Quedando únicamente cinco de ellos ahora es posible visitar todos los puentes realizando un camino euleriano (ruta que comienza y termina en distintos puntos), aunque continua siendo imposible realizar un ciclo euleriano (comenzando y terminando en el mismo punto).

La ruta en Google Maps con la nueva funcionalidad "A pie" quedaría como en la imagen, nada elegante y un poco caótica debido a que uno de los puentes es una autopista, pero al menos se podrían recorrer todos los puentes cruzandolos una sola vez. La posibilidad de empezar y terminar en un mismo punto, continúa siendo imposible.

1 comentario: