Problema de los puentes de Königsberg

Keywords: Problema de los puentes de Königsberg, 1736, Kaliningrado, Leonhard Euler, Prusia, Rusia, Siglo XVIII, Teoría de los grafos

El problema de los siete puentes de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) fue resuelto por Leonhard Euler en 1736 y dio origen a la Teoría de los grafos.

Consiste en lo siguiente:

Dos islas en el río Pregel, en 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 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 los grafos esta idea se corresponde con la posibilidad de encontrar un Ciclo Euleriano en un grafo.

Mapa de Königsberg

Imagen no existente
Puentes_Kronigsberg_mapa.jpg
Image:puentes_Kronigsberg_mapa.jpg

Este mapa de Königsberg de la época de Euler muestra donde se encontraban los siete puentes (en verde claro) y las ramas del río (en azul cielo).

Enlaces externos

• Mapas de Königsberg: Mapas de la época de Leonhard Euler y actuales.

Keywords: Problema de los puentes de Königsberg, 1736, Kaliningrado, Leonhard Euler, Prusia, Rusia, Siglo XVIII, Teoría de los grafos