LOS PUENTES DE KÖNIGSBERG

La ciudad de Kaliningrado, antiguamente llamada Königsberg, es un bonito lugar situado en la desembocadura del río Pregolya, en la antigua Prusia Oriental. Este río atravesaba la ciudad, diviendo la zona en varias partes. Para no perder la comunicación, ésta estaba llena de un sistema de puentes conectores.

En total, había siete grandes puentes en Kaliningrado: El puente del herrero, el puente conector, el puente verde, el puente del mercado, el puente de madera, el puente alto y, por último, el puente de la miel. Los ciudadanos se sentían muy orgullosos de esta gran red de comunicación, y entre ellos surgió un pequeño juego para entretenerse en los momentos de aburrimiento:


¿Se pueden atravesar todos los puentes pasando sólo una vez por cada puente?

Por aquella época, estaba en la ciudad un eminente matemático trabajando en la Academia Prusiana de las Ciencias. Como no podía ser de otra forma, enseguida se interesó por este acertijo y se propuso dar una solución mucho más completa y demostrativa de porqué es imposible cruzar todos los puentes sólo una vez. Este personaje se llamaba Leonhard Euler, posiblemente el mayor matemático de la historia.

En primer lugar, Euler simplificó el mapa del territorio a simplemente unas cuantas líneas y puntos. Eliminó todo lo sobrante:



Como podemos ver, los distintos territorios en los que los puentes dividieron la ciudad se convirtieron en puntos, es decir, en “vértices”; y los puentes se convirtieron en líneas, lo que llamamos “aristas”. También determina que hayun punto de “inicio” y un punto de “salida”.

Euler consiguió, a partir de este sencillo esquema, encontrar la solución de una forma mucho más elegante que la que aplicamos en un principio: Para poder recorrer un sistema de este tipo, los vértices “intermedios” deben tener un número par de aristas. Es decir, deben tener una vía para entrar y una vía para salir. Sólo los puntos de inicio y salida pueden tener un número impar de aristas, porque, evidentemente, nunca “entramos” al punto de inicio y nunca “salimos” del punto de llegada.

Es algo muy sencillo, vamos a crear mentalmente un sistema en el que hay un territorio divido en dos partes por un puente. ¿Cómo lo resolvemos? Tenemos que salir una vez del punto de inicio (nº impar), entrar en un punto intermedio y salir de él (nº par) y acabar entrando en el punto de salida (nº impar).

¿Y dónde reside la genialidad de Euler? En que este método se aplica a cualquier problema de este tipo.Con calcular las aristas que tienen los puntos intermedios y extremos podemos saber a la primera si el problema es irresoluble o no. En el caso de los puentes de Königsberg, los vértices intermedios tienen un número impar de aristas, por lo que es absolutamente imposible realizar la hazaña del ejercicio planteado.

También cabe destacar un último punto respecto al número de aristas que contienen los vértices de salida y llegada en un recorrido que sí se pueda completar (es decir, todo lo contrario a los puentes de Königsberg). Teniendo en cuenta que los vórtices intermedios tienen un número par de aristas, los vórtices de inicio y salida pueden tener, según la situación, un número par o impar de aristas:

– Si el punto de llegada y salida es el mismo, obligatoriamente debe tener un número par de aristas (uno para salir y otro para regresar). Esto se conoce como “ciclo euleriano”.

– Si por el contrario el punto de salida y el de llegada son diferentes, deben tener obligatoriamente un número impar de aristas. Esto es lo que conocemos como “camino euleriano”.

Estos estudios realizados por Euler fueron el detonante de la teoría de grafos, convirtiendo una simple discusión pueblerina en toda una disciplina científica.