Problema de los 7 puentes de Konisberg. Planteamiento e imposibilidad de resolución

El señor que sale en la imagen (abajo a la derecha) es Leonhard Euler. Se trata del principal matemático del siglo XVIII y uno de los más grandes y prolíficos de todos los tiempos, muy conocido por el número de Euler (e), número que aparece en muchas fórmulas de cálculo y física. A él también se le deben la forma actual de escribir las funciones f(x), las funciones trigonométricas (sen x y cos x, por ejemplo) y su relación con los números complejos a través de la fórmula que lleva su nombre. Pero este artículo no trata de las investigaciones de Euler sino de la resolución que dio a un problema célebre en aquella época.

El problema dice así: Dado el mapa de Königsberg, con el rí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? (ver mapa de Königsberg en la imagen)

Euler resolvió este problema en 1736 y lo más importante no es la solución en sí, que podía ser abordado por fuerza bruta, sino el método que utilizó: simplificó el mapa de la ciudad convirtiéndolo en cuatro puntos que son las cuatro regiones en las que el río divide la ciudad y trazó líneas uniendo esos puntos de forma equivalente a como los puentes unen las regiones de la ciudad. En este momento del texto es conveniente que mires el mapa de la ciudad y el diagrama de puntos y líneas de la imagen del encabezado y pienses en su equivalencia. (pista: el punto de la izquierda equivale a la isla central)

Una vez simplificado el mapa, estudió las líneas que salen y llegan a los puntos. Consideró que para cumplir las condiciones del problema debía empezar y terminar en un mismo punto, y el resto de puntos debían ser de paso intermedio. Pues bien: a estos puntos de paso intermedios necesariamente deben llegarles una cantidad par de líneas. Si no fuera así, se daría la situación de que al llegar a ese punto no podríamos salir de él por un camino diferente.

¿Y que pasa con el punto de inicio y de final? Pues que esos podrían tener una cantidad impar de líneas (salir de un sitio y no volver a pasar por ahí, o terminar en un sitio sin tener que salir de ahí), pero como el problema exige que comience y termine en el mismo sitio también han de ser pares porque hay que volver al punto de partida por un camino diferente.

Euler concluyó que no es posible recorrer el mapa como pide el problema porque el diagrama en el que él simplificó el problema tiene todos los puntos con un número impar de líneas (tres puntos tienen tres líneas y el otro tiene cinco). La forma de abordar este problema dio lugar a la teoría de grafos tan utilizada en programación. Al diagrama de puntos y líneas se le llama grafo, los puntos son vértices del grafo y las líneas se denominan aristas.

Hoy en día Königsberg se llama Kaliningrado, ya no está en Prusia sino en Rusia. En la Segunda Guerra Mundial se destruyeron dos puentes, posteriormente se remodelaron otros dos, de modo que en lugar de los siete puentes del problema original hoy en día solo quedan cinco. Esto ha cambiado la fisonomía de la ciudad y el problema hoy en día sigue siendo irresoluble con la condición de empezar y terminar en el mismo sitio, pero sí se puede cumplir si empiezas en un sitio y permites terminar en otro.

La estructura de este artículo, las imágenes y su contenido está sacado de la entrada de la wikipedia "Problema de los puentes de Königsberg" es.wikipedia.org/wiki/Problema_de_los_puentes_de_Königsberg