Euler y los siete puentes de Königsberg

Se trata de un célebre problema resuelto matemáticamente por Leonard Euler en 1736.

El río Pregel, también llamado Pregolya, a su paso por Königsberg (ciudad alemana de la Prusia Central en esos años, y hoy Kaliningrado perteneciente a Rusia), se bifurcaba en varios ramales formando dos islas antes de seguir su curso de nuevo. En el siglo XVIII ambas islas se conectaban entre sí y con las orillas del río por siete puentes, tal y como muestra la Figura 1.

Figura 1. Mapa de Königsberg en la época de Leonhard Euler, que muestra dónde se encontraban los siete puentes (en verde claro) y las ramas del río (en celeste).

Se dice que sus habitantes intentaron durante años encontrar una ruta por la que cruzando una sola vez cada puente se pudiese regresar al punto de partida. Nunca lo encontraron. La cuestión es ¿existe tal camino? Alguno dirá: ¡eso es posible, sin duda!, otros que: ¡no, eso es imposible! Pero… ¿cómo demostrar quién tiene razón? En su propuesta Euler lo hizo de una forma general para cualquier número de puentes, sean siete o más.

Era la primera vez que se hacía referencia a una geometría basada en la estructura de los objetos y no en las medidas que suele ser lo habitual. Euler la llamó “geometriam situs”, hoy más conocida como Topología, dando lugar a la teoría de grafos o teoría de las gráficas. Un grafo se define como un conjunto de objetos llamados vértices (o nodos) y una selección de aristas (o arcos). Se suele representar mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

El problema de los siete puentes de Königsberg es un problema complejo pero con una solución muy simple de entender. No vamos a entrar muy a fondo en la explicación pero si en el modo de llegar a ella.

Figura 2

En la Figura 2 se muestran de manera esquemática los 7 puentes, 1,2,3,4,5,6, y 7, y las cuatro zonas, A,B,C,D, incluidas las dos islas, Isla 1 e Isla 2, en que el río Pregel divide a la ciudad.

Lo primero que hizo Euler para resolver el problema fue eliminar todo lo que no era importante. Convirtió las cuatro zonas (A, B, C y D) en puntos (los llamados vértices o nodos), y cada uno de los puentes (1,2,3, …) en líneas (aristas o arcos) que conectan los nodos (zonas). De esta manera obtuvo el gráfico indicado en la Figura 3. El problema lo redujo a decidir si existe o no un camino que comience por uno de los puntos azules, transite por todas las líneas una sola vez, y regrese al mismo punto de partida.

La conclusión básica de su teoría, que no de su demostración, es muy sencilla:
“Para cumplir con las condiciones del problema, si uno llega a un nodo (zona) a través de una arista (puente) debe salir de él por una arista distinta (puente), lo que nos lleva a que en cada nodo (zona) el número de aristas que confluyen debe ser par”.

En el caso de los puentes de Königsberg esta premisa no se cumple en ningún caso: a los nodos (zonas) B, C y D llegan tres aristas (puentes), mientras que al nodo (zona) A llegan cinco. Según la conclusión de Euler se trata de un problema irresoluble: no existe solución que permita hacer el recorrido pasando una sola vez por cada uno de los puentes.

Pero no todos somos Euler ni tenemos por qué conocer sus teorías. A primera vista parece que lo más fácil para intentar resolver el problema sería efectuar todas las pruebas posibles, numerar las rutas y ver cuales pueden ser válidas. Pero esta forma de actuar llevaría demasiado tiempo. No digamos nada si el número de puentes es superior a siete. Necesitamos buscar otro método más sencillo.

Imaginemos que queremos hacer un recorrido tal como ABDC y vuelta a la zona A. Designaremos por AB el paso de la zona A a la B sin distinguir de momento el puente por el que queremos pasar (habría dos opciones: 6 o 7). Lo mismo con los pasos BD, DC y CA, momento en el que alcanzaríamos de nuevo a la zona A. Al trayecto completo que hemos hecho por las 4 zonas lo podríamos denominar ABCDA, que contiene 5 letras y por el que hemos cruzado 4 puentes. Siguiendo esa misma regla, si fuesen 5 los puentes el camino tendría seis letras, y así sucesivamente. Por tanto, una primera conclusión sería que si pasamos una sola vez por los 7 puentes de Kögnisberg la ruta o trayecto deberá designarse con 8 letras. En general, si tenemos n puentes para asignar su ruta se necesitarán n+1 letras.

Ahora queda lo más difícil. ¿Cómo y en que orden deberán ir las letras para cumplir con lo exigido? Entre las orillas A y B hay dos puentes por lo que tendrá que figurar la sucesión AB o BA dos veces, una para indicar el paso por un puente y la otra por el otro. Lo mismo sucederá con A y C (también hay dos puentes). Para el resto de pasos entre zonas solo existe un puente y las sucesiones AD, BD y CD (o las inversas) solo figurarán una vez en la designación de la ruta.

En resumen, para que el problema tenga solución, una segunda conclusión es que:
a) La ruta se designe mediante ocho letras,
b) En su distribución se encuentren incluidas las secuencias de orden citadas antes.

Otro aspecto muy importante a tener en cuenta es el número de puentes de cada zona porque en función de ese dato sabremos el número de veces que deberá estar repetida una letra determinada. En nuestro caso la zona A tiene 5 puentes, por lo que la letra A estaría repetida 3 veces. Las tres zonas restantes B, C y D tienen 3, y estas letras estarían repetidas 2 veces cada una.

A la vista de lo expuesto podemos establecer una regla o tercera conclusión: Si el número de puentes que atraviesa una determina zona es impar, el número de veces que se repetiría la letra de esa zona sería el equivalente a añadir a dicho número impar una unidad y dividir la suma obtenida por dos.

O sea:
la letra A figurará  (5 + 1)/2, o sea 3 veces;
la letra B             (3 + 1)/2, o sea 2 veces
la letra C             (3 + 1)/2, o sea 2 veces;
la letra D             (3 + 1)/2, o sea 2 veces;

Por tanto, en el caso de que pasásemos una sola vez por cada uno de los siete puentes, la ruta o trayecto tendría un total de 9 letras. Como también hemos dicho que para que el problema tenga solución la asignación del trayecto debería tener un máximo de 8 letras, está claro que existe una contradicción y el problema de los siete puentes de Königsberg es un problema irresoluble.

¿Significa esto que cuando tenemos una isla, dos brazos y siete puentes no existe solución alguna? Claro que no. Hemos demostrado que no la tiene para una situación concreta. Con otra ubicación de los puentes la respuesta puede ser muy distinta.

Para los aficionados a la historia decir como colofón que los nombres de los 7 puentes de Königsberg eran: Puente del herrero, Puente conector, Puente verde, Puente del mercado, Puente de madera, Puente alto y Puente de la miel. Dos de esos siete puentes originales fueron destruidos por el bombardeo de Königsberg durante la Segunda Guerra Mundial. Otros dos fueron demolidos más tarde y reemplazados por carreteras. Los tres puentes restantes aún permanecen en pie, aunque sólo dos de ellos son del siglo XVIII porque el tercero también fue reconstruido en 1935.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: