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 siglo XVIII 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 de madera, 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 los puentes, y regresando al mismo punto de inicio.

Contextualización del problema

Leonhard Euler llegó a Prusia en 1741, a la edad de 34 años, donde vivió hasta 1766 para luego regresar a San Petersburgo. Durante esos años trabajó en la Academia Prusiana de las Ciencias, donde desarrolló una prolífica carrera como investigador. Euler fue contemporáneo de varios otros famosos matemáticos y pensadores procedentes de aquella ciudad, tales como Immanuel Kant, Johann Georg Hamann y Christian Goldbach, por lo que Königsberg fue en ese tiempo un importante epicentro científico.

Es en este ambiente y por estos años en que surge la formulación del problema de los puentes de Königsberg, propagándose a modo de juego y de trivia matemática entre los intelectuales de la época

Análisis y solución del problema

El problema, formulado originalmente de manera informal, consistía en responder a la siguiente pregunta:

La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede 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 «Solution problematis ad geometriam situs 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 de Königsberg.

Para dicha demostración, Euler recurre a una abstracción del mapa, enfocándose exclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente lo representó mediante una línea que unía a dos puntos, cada uno de los cuales 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 azules, transite por todas las líneas una única vez, y regrese al mismo punto de partida.

Solución de Euler

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.

En particular, como en este diagrama los cuatro puntos poseen un número impar de líneas incidentes (tres de ellos inciden en tres líneas, y el restante incide en cinco), entonces se concluye que es imposible definir un camino con las características buscadas