La Enciclopedia Libre Universal en Español dispone de una lista de distribución pública, enciclo@listas.us.es
Problema de los puentes de Königsberg
Artículo de la Enciclopedia Libre Universal en Español.
El problema de los siete puentes de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) fue resuelto en 1736 por Leonhard Euler y dio origen a la teoría de grafos.
Consiste en lo siguiente:
En la ciudad de Königsberg hay una isla y el río que la rodea se divide en dos brazos. La distintas zonas de tierra están unidos mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?
Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo sin repetir las líneas?
Euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par. En teoría de grafos esta idea se corresponde con la posibilidad de encontrar un camino euleriano en un grafo.
