Kaliningrado es una ciudad rusa de la que hemos oído hablar este verano, cuando la Selección Española de fútbol se desplazó allí a jugar el partido contra Marruecos.
Esto da pie a contar algunas curiosidades sobre esta ciudad. La primera es sobre su ubicación geográfica: está separada del resto de Rusia por Lituania -al norte-, pero se considera una ubicación estratégica, porque proporciona una salida al mar Báltico, con un puerto que no se congela en invierno. Hasta la Segunda Guerra Mundial perteneció a Alemania en el territorio de Prusia, llamándose Königsberg. Pero también está separada del resto de Alemania por Polonia -al sur-. Con más de 700 años de historia, esta ciudad cuenta con varias universidades, y fue la cuna de personas famosas como el filósofo Kant, el compositor Hoffmann, el físico Kirchhoff, y el matemático Hilbert.
La que nos interesa aquí es el problema de sus siete puentes, que se planteó en el siglo XVIII. La ciudad se extiende a ambas orillas del río Pregolya y además ocupa dos islas del río. Hay un puente entre ambas islas, la isla menor tiene además 4 puentes, dos hacia cada orilla, y la mayor cuenta también con un puente hacia cada orilla del río. En una época en la que la ciudad era el epicentro científico, se planteó un problema entre eruditos, a modo de divertimento matemático. El problema lo podemos expresar así: “Se invita a los paseantes de los domingos por la mañana a recorrer la ciudad inventando un recorrido que pase por cada uno de los siete puentes, sin atravesar dos veces ninguno de ellos.” Aparte de venir bien el paseo para quitarse el frío, se tenía la certidumbre de que ninguno lo había conseguido, pero ¿por qué?
Euler proporcionó la solución unos meses más tarde, sin usar la “fuerza bruta”, es decir, sin necesidad de listar una por una todas las combinaciones de recorridos posibles. Llegó a la conclusión de que no existía tal recorrido, comenzando con una abstracción del mapa de la isla, algo así como esta: Comenzamos representando los cuatro barrios o zonas de la ciudad como puntos, y los siete puentes como cuerdas que los unen. Esto se llama grafo en matemáticas, y se considera que la teoría de grafos nació de la mano de Euler en relación a este problema. Ahora nos toca ordenar las cuerdas para resolver el problema. Si imaginamos cualquier recorrido como una cuerda que tiene un principio y un final, en los puntos en los que se cruce (barrios) la cuerda se podrá cruzar (entrar y salir del barrio), pero tendrá que salir y tantas veces como entre, y por tanto en la representación gráfica veremos un numero par de líneas conectándolo con otros puntos. Bueno, en realidad puede haber dos excepciones: si iniciamos el recorrido y lo finalizamos en barrios distintos, el inicio aportará una sola cuerda (salida) al grafo en cuyo caso podremos ver un número impar de líneas en el barrio donde se inicia el recorrido: una representando la salida, y dos más por cada paso posterior por ese barrio. Lo mismo ocurre en el final del recorrido: se representará por un número impar de líneas salvo que coincida con el inicio.
Por ejemplo, en otra ciudad imaginaria, representada en el dibujo siguiente es fácil ver que los puntos superior e inferior son puntos al los que llega un número par de líneas (2), es decir, son barrios por los que se pasa una sola vez (se entra y sale una vez), el punto central representa un barrio al que se debe entrar y salir dos veces. El punto de la derecha es un barrio que solo puede ser inicio o final del recorrido. Por último, el punto de la izquierda será un punto de entrada y salida, y además será inicio o final del recorrido. Por tanto, podemos decir que en un grafo de estas características solo haber dos puntos con un número impar de líneas, o ninguno, si es que el inicio y el final del recorrido coinciden. Por tanto, echando un vistazo rápido al grafo de los puentes de Königsberg vemos rápidamente que los dos puntos que representan los barrios de las orillas del río tienen 3 cuerdas (tres puentes a cada orilla), una de las islas tiene también tres cuerdas, y la otra cinco. ¡Los cuatro puntos tienen un número impar de cuerdas! Ahí está. No podemos identificar un solo inicio y un solo final del recorrido, y por eso concluimos que es imposible.