4.7.03


445.- EULER Y LOS PUENTES DE KÖNIGSBERG


La ciudad de Königsberg está dividida en cuatro zonas por el río Pregel, con siete puentes que las conectan. Un problema clásico era encontrar un camino que los recorriese todos, pero pasando sólo una vez por cada puente.



La solución la encontró Euler (y con ella comenzó la teoría de grafos), y fue una sorpresa por partida doble:

-Primero, alguien había resuelto el problema.
-Segundo, la solución era que no había solución! Es decir, no había un recorrido como el que se pedía.

Este tipo de solución fue novedosa. Fue una de las primeras de las que prueban la 'no-existencia' de algo, hasta el momento se asumía sólo la incapacidad propia para no hallar la solución, y no se cuestionaba que el problema fuera irresoluble. El concepto de solucionar un problema demostrando que no tenía solución fue realmente original, y desde entonces se lo ve en distintos problemas de mayor o menor importancia (dos de los que hablé en algún momento, fórmulas para las raíces de un polinomio de grado mayor que cuatro, o algoritmos numéricos para calcular trayectorias a largo plazo de cohetes o satélites).

Más sobre el problema, generalizaciones, la solución, etc. en ésta página, o en ésta otra (de la cual tomé la imagen que ilustra el post).