Mapa deKönigsberg en la época deLeonhard Euler, que muestra dónde se encontraban los siete puentes (en verde claro) y las ramas del río (en celeste).
Elproblema de los puentes de Königsberg, también llamado más específicamenteproblema de los siete puentes de Königsberg, es un célebreproblema matemático resuelto porLeonhard Euler en 1736 y cuya resolución dio origen a lateoría de grafos.[1] Su nombre se debe aKönigsberg, la ciudad dePrusia Oriental y luego deAlemania que desde 1945 se convirtió en la ciudadrusa deKaliningrado.
Esta ciudad está atravesada por elrío Pregolia. Este se bifurca y rodea con sus brazos a la islaKneiphof,[2] de forma que el terreno queda dividido en cuatro regiones distintas, que entonces estaban unidas mediante siete puentes llamados puente del herrero, Puente Conector, Puente Verde, Puente del Mercado, Puente de Madera, Puente Alto y Puente de la Miel.[3] El problema se formuló en el siglo XVIII y consistía en encontrar un recorrido para cruzar a pie toda la ciudad pasando solo una vez por cada uno de los puentes y regresando al mismo punto de inicio.[4]
Leonhard Euler llegó a Prusia en 1741, a la edad de 34 años, donde vivió hasta 1766 y luego regresó aSan Petersburgo. Durante esos años trabajó en laAcademia Prusiana de las Ciencias, donde desarrolló una prolífica carrera como investigador.[5] Euler fue contemporáneo de varios otros famosos matemáticos y pensadores procedentes de aquella ciudad, comoImmanuel Kant,Johann Georg Hamann yChristian Goldbach, por lo que Königsberg fue en ese tiempo un importante centro científico.
Fue así como surgió la formulación del problema de los puentes de Königsberg, que se propagó a modo de juego y de problema matemático entre los intelectuales de la época.
Leonhard Euler (1707-1783), famoso matemático que resolvió el problema en 1736, dando origen a lateoría de grafos. Retrato de 1753.
El problema, formulado originalmente de manera informal, consistía en responder a la siguiente pregunta:
Dado el mapa deKönigsberg, con elrío Pregel 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 solo 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 problema puede resolverse aplicando un método defuerza bruta, lo que implica probar todos los posibles recorridos existentes. Sin embargo,Euler, en 1736, en su publicación«Solutio problematis ad geometriam situs pertinentis»,[1] demuestra una solución generalizada del problema, que puede aplicarse a cualquier territorio en el que ciertos accesos estén restringidos a ciertas conexiones, como el de los puentes de Königsberg.
Para dicha demostración, Euler recurre a una abstracción del mapa y se enfoca exclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente quedó representado mediante una línea que unía a dos puntos, y cada uno de estos puntos representaba una región diferente. Así, el problema se reduce a decidir si existe o no un camino que comience por uno de los puntos, recorra todas las líneas una sola vez y regrese al mismo punto de partida.
Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible necesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados con un número impar de líneas. Sin embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no podría existir ningún punto conectado con un número impar de líneas.[nota 1]
En particular, como se ve en este diagrama, los cuatro puntos tienen un número impar de líneas (tres de ellos tienen tres líneas y el restante tiene cinco). Por lo tanto, se concluye que es imposible definir un camino con las características buscadas que son los siete puentes de Königsberg.
En lateoría de grafos existe un concepto llamadociclo euleriano, llamado así justamente en honor a Leonhard Euler, que representa cualquier camino dentro de un grafo particular capaz de recorrer todas las aristas una sola vez y regresar finalmente al mismo vértice original. Encoloración de grafos, una subárea de la teoría de grafos, la resolución de este problema constituye además el primer teorema de losgrafos planares.[6]
Por otra parte, la publicación de Euler es la primera que hace alusión a unageometría en que solo interesan las propiedades estructurales de los objetos y no sus medidas, como tradicionalmente se hace. El matemático llama a esta nueva manera de ver los objetos geométricos «geometriam situs», término que hoy se traduce comotopología,[2] área actual de la matemática cuyo origen directo puede situarse en la resolución de este problema.[7]
Dos de los siete puentes originales fueron destruidos por elbombardeo de Königsberg durante laSegunda Guerra Mundial. Otros dos fueron posteriormente demolidos y reemplazados por carreteras modernas. Los tres puentes restantes aún permanecen en pie, aunque solo dos de ellos desde la época de Euler, pues uno fue reconstruido en 1935.[8]
Por lo tanto, en la actualidad solo existen cinco puentes enKaliningrado, distribuidos de tal manera que ahora sí es posible definir uncamino euleriano, es decir, una ruta que comienza en una isla y termina en otra; pero no todavía unciclo euleriano, es decir, que la ruta comience y termine en el mismo lugar, lo cual era necesario para cumplir con las condiciones iniciales del problema.[9]
↑En realidad, en estos recorridos, llamadosciclos eulerianos, no pueden existir puntos con un número impar de líneas incidentes. Solo en el caso de loscaminos eulerianos, donde se acepta que el punto inicial y el final sean distintos, puede darse que únicamente estos tengan un número impar de líneas incidentes. Euler solo caracterizó formalmente los caminos eulerianos; la caracterización formal de ciclo euleriano la hizoCarl Hierholzer más tarde, en 1873, lo que no impide que la demostración de Euler sea general y correcta. Fuente:Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976).Graph Theory 1736-1936(en inglés). Oxford: Clarendon Press. pp. 239.
↑Dunham, William (1999).Euler: The Master of Us All. The Mathematical Association of America. pp. xxiv-xxv.
↑Alexanderson, Gerald (julio de 2006). «Euler and Königsberg's bridges: a historical view».Bulletin of the American Mathematical Society.
↑Pappas, T. "Königsberg Bridge Problem & Topology." The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 124-125, 1989.
↑Taylor, Peter (diciembre de 2000). Australian Mathematics Trust, ed.«WhatEver Happened to Those Bridges?». Archivado desdeel original el 14 de noviembre de 2009. Consultado el 12 de abril de 2010.
