El Problema De Los Puentes De Königsberg

Problema de los puentes de Königsberg
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 Euler en 1736 y cuya resolución dio origen a la teoría de grafos. Su nombre se debe a Königsberg, el antiguo nombre que recibía la ciudad rusa de Kaliningrado, que durante el sigloXVIII formaba parte de Prusia Oriental, como uno de los ducados del Reino de Prusia.
Esta ciudad es atravesada por el río 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 demadera, 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 sólo una vez por cada uno de lospuentes, y regresando al mismo punto de inicio
Análisis y solución del problema
El problema, formulado originalmente de manera informal, consistía en responder a la siguiente pregunta:
Dado el mapa deKönigsberg, con el río Pregolya 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, recorriendo sólo 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 problemapuede 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 geometriamsitus pertinentis» demuestra una solución generalizada del problema, que puede aplicarse a cualquier territorio en que ciertos accesos estén restringidos a ciertas conexiones, tales como los puentes...