Los puentes de Königsberg

koenigsberg

La actual Kaliningrado fue fundada en 1255 a orillas del río Pregel. Con el nombre de Königsberg, fue la capital de Prusia hasta 1701, cuando la trasladaron a Berlín. Capital del óblast ruso de Kaliningrado, es destacable por haber dado a luz a Immanuel Kant, por ver la primera impresión del Catecismo Luterano o por sus puentes, los siete puentes de Königsberg.

Un río, dos islotes y siete puentes. ¿Qué interés puede haber en ellos? Aparentemente no es algo que llame la atención a cualquiera. Pero en el siglo XVIII se había planteado un problema en el que estos puentes, el río y los islotes, eran los protagonistas:

En la ciudad de Königsberg, Prusia, hay una isla llamada Kneiphhof, rodeada por el río Pregel. Hay siete puentes […] que cruzan el río en su bifurcación. La pregunta es si una persona puede realizar un paseo de manera que cruce cada uno de los puentes una única vez. Se dice que mientras que algunos niegan la existencia de dicho camino y otros dudan, nadie declara que sea posible.

Este párrafo, escrito como una sencilla introducción al desarrollo que a continuación se presentaba, dio paso accidental y fortuitamente a la topología y a la teoría de grafos. Son ramas de las matemáticas orientadas al estudio de la forma intrínseca de los objetos en cuestión; no de medidas relacionadas con sus distancias o sus ángulos. Esta manera de ver la geometría, mucho más abstracta de lo que hasta el momento se había estudiado, se basaba —muy tangencialmente— en lo que Leibniz había llamado geometría de la posición, geometria situs, pero hasta 1736 no se acuñó el término con el sentido que hoy día tiene.

Leonhard Euler nació en Basilea, Suiza, el 15 de abril de 1707. Con trece años entró en la universidad de su ciudad natal y con dieciséis obtuvo el título de Máster en Filosofía, especializado en Descartes y Newton. Mientras tanto, recibía clases de Johann Bernoulli, matemático al que se le deben algunas de las primeras aportaciones al cálculo infinitesimal, desarrollado pocos años antes por Newton y Leibniz. Fue Bernoulli quien descubrió la facilidad de Euler para las matemáticas y lo recomendó para una plaza en la Academia de Ciencias de Rusia en San Petersburgo. Tenía veintiséis años cuando lo nombraron jefe del departamento de matemáticas.

euler

Ocho años después se mudó con su esposa a la capital prusiana, Berlín, donde Euler había obtenido una plaza en la Academia de Ciencias de Prusia, otorgada por Federico el Grande. Veinticinco años después, debido a un conflicto entre Euler y varios pensadores presentes en la misma academia —como Voltaire, tan sofisticado para Euler—, abandonó Berlín y volvió a la capital rusa. Fue allí donde, en 1783 murió de una hemorragia cerebral.

A lo largo de su vida, Euler escribió sobre mecánica, sobre dinámica de fluidos, sobre óptica, sobre astronomía, sobre medicina. Pero por lo que lo hemos sacado a relucir en estas líneas es por sus matemáticas, por su geometría y sus grafos, por su Solutio problematis ad geometriam situs pertinentis, por su solución al problema de los puentes de Königsberg.

Euler no consideraba difícil el problema, pero lo atrajo la relación que tenía con lo que Leibniz llamaba geometría de la posición. Pensó en cómo generalizar ese problema además de en dar una respuesta a la pregunta del problema: ¿se podría realizar un recorrido por los siete puentes pasando una única vez por cada uno de ellos? Presentó su solución en 1736. Su planteamiento, Solutio problematis ad geometriam situs pertinentis, lo dividió Euler en veintiún párrafos y fue finalmente publicado en 1741 en la revista Commentarii academiae scientiarum Petropolitanae.

Una primera observación que hace Euler es que una manera de ver si el problema tiene solución es anotar todos los recorridos posibles. El incoveniente de este método no es sólo la enorme cantidad de tiempo que podría requerir sino que además no es aplicable a una configuración alternativa de los puentes o los islotes. Así que decide buscar otras vías. Una primera medida que toma es la de simplificar el problema. No importa cuán largos sean los puentes, ni las diferencias que haya entre ellos, ni entre las islas. Lo único relevante es la relación entre los puentes y las islas y orillas del río.

esquema

Para representar la situación emplea un esquema que resulta completamente novedoso. Realiza también un cambio en la notación habitual: además de llamar a los puentes a, b, c, d, e, f y g, llama a los bloques de tierra (las dos orillas y las islas) A, B, C y D. Con esta nueva notación, AB significa cruzar desde el bloque de tierra A hasta el bloque B; si a continuación se desea cruzar a D, se puede denotar como ABD. Así, siempre que se cruce otro puente, se añade otra letra a la lista. Como el problema en cuestión cuenta con siete puentes, requerirá una lista de ocho letras.

Destaca que a esta notación no le afecta que haya dos o más puentes que comuniquen dos zonas. Si se desea cruzar de A a B, no importa por qué puente se realice el desplazamiento, por lo que la notación no se ve condicionada. Da también detalles sobre el caso particular en cuestión. Explica que los pares (A,B) y (A,C), tienen que ir seguidos el uno del otro en la lista que represente la solución exactamente dos veces, independientemente de qué letra se posicione en primer lugar. De manera análoga, (A,D), (B,C) y (C,D) tienen que aparecer juntos.

esquema2

Observa ahora que para dar una respuesta al problema necesita ora encontrar la lista de ocho letras que represente el orden en que cada bloque sería recorrido, ora probar que no existe tal secuencia. Procede a partir de la nueva figura. Representa una situación más sencilla que la del problema original, pero le proporciona un método para analizar la posible solución. Euler considera que si se cruza el puente a —en la nueva figura— una única vez, la región A habría de ser el comienzo o el final de este cruce. Ahora, si los puentes a, b y c se cruzan una única vez, por la región A se pasará exactamente dos veces —es indiferente si se acaba o se empieza en A—. De manera similar, si son cinco los puentes que llevan a A, dicha región aparecerá tres veces en la secuencia solución. Generaliza que “si el número de puentes es un número impar cualquiera y lo incrementamos en 1, entonces el número de veces que aparece A es la mitad del resultado”, es decir, si n es el número de puentes que llegan a A, el número de veces que se pasará por A en el recorrido viene dado por

\frac{n+1}{2}

Con este hecho Euler resuelve el problema. Son cinco los puentes que llevan a A, por lo que aparecerá en la secuencia 3 veces. Análogamente, a las regiones B, C y D llegan 3 puentes; aparecerán 2 veces cada una. Así pues, se pasará 3 veces por A, 2 veces por B, otras 2 por C y 2 también por D, lo que da un total de 9 regiones en la solución. Pero Euler ya había mostrado que el hecho que sólo hubiera 7 puentes hacía condición necesaria que sólo habría 8 regiones en la secuencia. Esta contradicción fue la prueba que presentó Euler. Había demostrado que el problema de los puentes de Königsberg no tenía solución.

De los veintiún párrafos que redacta en su Solutio problematis ad geometriam situs pertinentis, con este desarrollo tan sólo llena unos diez. Lo que ahora se propone Euler es dar el planteamiento general. Comienza con la observación de que si a todas las porciones de tierra llega un número impar de puentes, estamos en condiciones de decir si se pueden recorrer todas pasando por cada puente una única vez. Hay dos posibilidades. Si sumamos el número total de veces que cada región debe ser recorrida y el resultado es igual al número de puentes incrementado en una unidad, entonces el recorrido deseado se puede realizar. Si por el contrario esta suma es mayor que el número de puentes más uno, entonces el problema no tiene solución —como en el caso de los puentes de Königsberg—. Euler trata ahora el caso en el que alguna de las regiones tiene un número par de puentes que la comunican, posibilidad no considerada en el problema de Königsberg. Sea X una porción de tierra comunicada por dos puentes. Puede ser que X sea el inicio del recorrido, en cuyo caso aparecería dos veces en la secuencia: en el inicio y en el final; y puede que no sea el inicio, por lo que aparecería una única vez —el recorrido llegaría a X por uno de los puentes y tendría que salir necesariamente por el otro—. Se puede razonar de manera similar para el caso en que a X llegan cuatro puentes. Se deduce que si es el punto inicial, se recorrerá tres veces; si no, serán dos. En general, si a X llega un número par de puentes, pongamos n, y se encuentra en la posición inicial de la secuencia, el número de veces que se recorrerá será

\frac{n}{2}+1

Si X no es el punto de partida, el número de veces que aparecerá en el recorrido es

\frac{n}{2}

A partir de un ejemplo —que no trataremos hoy—, Euler muestra cómo se puede buscar, en una estructura cualquiera de porciones de tierra y puentes —él no lo dijo, pero es a eso a lo que ahora llamamos grafo—, un recorrido que pase por cada puente una única vez —es importante mencionar que a un recorrido con esta características es a lo que en la actual teoría de grafos se llama, en su honor, camino euleriano—, y en esto se basa para llegar, en el penúltimo párrafo, a sus tres conclusiones principales.

No vamos a entrar en ellas. Se trata de condiciones que da sobre el grafo, sobre la relación entre puentes y porciones de tierra, que implican la existencia o no existencia del camino euleriano. No obstante, sí hay algo llamativo en sus conclusiones: sólo demostró la primera. Deja las otras dos poco más que mencionadas; considera que no merece la pena dar detalles en lo que concierne a hallar la ruta, según sus propias palabras.

Euler nunca vio en este problema una dificultad extrema. Le pidieron ayuda para resolverlo y le extrañó que recurrieran a él, matemático, por la poca relación que apreciaba entre el problema y su área de conocimiento. Pero vio una oportunidad para esa geometría de Leibniz y, sin él pretenderlo, dio paso a toda una nueva rama de esa ciencia y arte de los números, los vectores, las funciones, los espacios y los conjuntos.

Este problema es tan banal, pero me pareció digno de atención en tanto que ni geometría, ni álgebra, ni siquiera el arte de contar fueran suficiente para resolverlo. De acuerdo a esto, me vine a preguntar si pertenecería a la geometría de la posición, por la que tanta predilección sintió Leibniz una vez.

Anuncios

2 Respuestas a “Los puentes de Königsberg

  1. Hmmm. Me sonaba ligeramente el tema y me ha resultado fascinante, aunque en algunos puntos se me hace algo duro de seguir el razonamiento.

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