3.2. Los puentes de Königsberg

Königsberg, actualmente llamada Kaliningrado, es una ciudad que se encuentra a orillas del Mar Báltico, en territorio ruso y a unos 50 kilómetros de la frontera con Polonia.

Fue una ciudad que sufrió duros ataques durante las dos guerras mundiales, con lo cual podéis imaginaros los graves daños que se produjeron.

Muchos de sus edificios históricos fueron derrumbados por bombardeos. En 1946, en la Conferencia de Berlín, la ciudad pasó a manos de la antigua URSS, que le cambió el nombre, un año después, por el de Kaliningrado.

Icono IDevice Galería de imágenes
Muestra Imagen Puente levadizo sobre el río Pregel. Imagen subida a Flickr con Licencia Creative Commons por sludgegulper
Puente levadizo sobre el río Pregel. Imagen subida a Flickr con Licencia Creative Commons por sludgegulper
Muestra Imagen Lagos del Castillo. Imagen subida a Flickr con Licencia Creative Commons por sludgegulper
Lagos del Castillo. Imagen subida a Flickr con Licencia Creative Commons por sludgegulper
Muestra Imagen The Houes of the Soviets. Imagen subida a Flickr con Licencia Creative Commons por sludgegulper
The Houes of the Soviets. Imagen subida a Flickr con Licencia Creative Commons por sludgegulper
Muestra Imagen Catedral de Königsberg. Imagen subida a Flickr con Licencia Creative Commons por dlisbona
Catedral de Königsberg. Imagen subida a Flickr con Licencia Creative Commons por dlisbona
Icono IDevice Curiosidad

Königsberg es famosa por ser el lugar de nacimiento del filósofo Kant, pero también es famosa por sus siete puentes y por el problema que consistía en saber si una persona podría cruzar todos los puentes una sola vez.

Este problema fue resuelto por Euler.

Además de Kant, en esta ciudad nacieron destacados científicos de los 3 últimos siglos, como son el físico Kirchoff y el matemático Hilbert.

David Hilbert nació en un pueblo cerca de Königsberg, estudió en la universidad de Königsberg y en la de Berlin, donde asistió las clases de Weiertrass y Kronecker.

Además de sus magníficos trabajos, es famosa la conferencia que dio en el Congreso Internacional de Matemáticas de París de 1900, en el que además de defender que las matemáticas eran una ciencia que podía desarrollarse independientemente de las demás, proponía sus famosos 23 problemas que ocuparían a la matemática del siglo XX. Aún hoy alguno de estos problemas no se ha resuelto.

Hilbert recibió muchos honores y en 1930 estando ya retirado, la ciudad de Königsberg le hizo ciudadano de honor. Son famosas sus palabras en las que se reconoce su entusiasmo por las matemáticas: "Debemos saber, así que sabremos". Estas mismas palabras se escribieron en su epitafio.


En el siglo XVII la ciudad de Königsberg estaba atravesada por el río Pregel que se dividía en el Viejo y en el NuevoPregel. Este río formaba dos islas a su paso por la ciudad, una de las cuales, la más pequeña, se llamaba la isla Kneiphof.

Mapa de la ciudad en tiempos de Euler
Mapa de la ciudad en el siglo XX
Königsberg en tiempos de Euler Kaliningrado. Siglo XX

 

Para unir las cuatro partes de la ciudad separadas por la geografía, existían siete puentes.

Se cuenta que los domingos por la mañana y los días de fiesta, los habitantes de la ciudad salían a pasear (presumiblemente, para tomar el sol, habida cuenta del frío que debía hacer en Königsberg, dada su situación geográfica) y se entretenían tratando de resolver el siguiente problema: ¿Es posible recorrer todas las zonas de la ciudad, atravesando todos los puentes, una y sólo una vez cada uno de ellos?

Prueba a resolverlo en la siguiente animación.

En la animación, aparece de forma esquemática la disposición de los puentes. La zona azulada corresponde al río, es decir, al agua y la verde a las zonas de tierra. Así, los puentes sería las siete franjas verdes que atraviesan la zona azul. Puesto que por el agua no podemos andar, tienes que intentar atravesar esas siete franjas verdes sin tocar las zonas azules.

Applet Descartes realizada por Salvador Calvo-Fernández Pérez bajo licencia Creative Commons.

Esta unidad interactiva requiere la máquina virtual de Java J2RE.
Icono de iDevice Ejemplo o ejercicio resuelto
Dibujo simplificado de la situación de las islas y los puentes

Euler, una vez enterado del problema gracias a un grupo de jóvenes de Königsberg que en 1735 le pidieron que resolviera el problema, se dedicó por completo al estudio del mismo, dando una solución simple e ingeniosa,que servía también para cualquier número de puentes.

Para empezar, Euler formuló el problema de la siguiente manera:

“En la ciudad de Königsberg, en Prusia, hay una isla A llamada Kneiphof, rodeada por los dos brazos del río Pregel.

Hay siete puentes a, b, c, d, e, f y g, que cruzan por los dos brazos el río. La cuestión consiste en determinar si una persona puede realizar un paseo de tal forma que cruce cada uno de estos puentes sólo una vez”.

 

A los pocos meses Euler presentó un voluminoso informe a la Academia rusa de San Petersburgo, en el que afirmaba haber demostrado la imposibilidad de tal ruta. Posteriormente, publicó un artículo titulado Solutio problematis ad geometriam situs pertinentis (Euler 1736), en el que resolvía el problema en el caso general, obteniendo condiciones generales para la existencia de soluciones para cualquier problema del mismo tipo.

Este artículo es considerado por varios autores como el nacimiento de la Teoría de Grafos, utilizada actualmente en una gran cantidad de aplicaciones, y también como una de las primeras manifestaciones de una nueva Geometría.

Fuente: Revista SUMA, n.º 45, febrero 2004.

Icono IDevice Para saber más

Para resolver el problema, según Euler, todo se basaba en utilizar una notación adecuada. Para ello, Euler llamó A, B, C y D a las distintas regiones de Königsberg. El camino que va desde A hasta B puede ser por el puente a o por el b, pero Euler lo designó por AB. Una vez allí, para ir a D, se sigue el camino BD, designando la trayectoria total por ABD, y así sucesivamente hasta recorrer todas las zonas y puentes, de manera que al final se obtendrá una combinación de ocho letras. Sin embargo, esta notación tiene un inconveniente, y es que no tiene en cuenta que para ir de una zona a otra puede que exista más de un puente.

Además, en dicha combinación de letras, el camino AB debería aparecer dos veces, ya que también está el BA; el camino CA habría de aparecer otras dos veces; y tan sólo una los caminos AD, BD, y CD. Por lo tanto, las letras A, B, C, D, deben formar una serie de ocho letras, apareciendo el número requerido de veces las combinaciones de las mismas.

Euler vio que esta situación concreta no era posible, ya que, por ejemplo, si se empieza en la región A, si esta región sólo conectara con el puente a, como puede que se llegue o se venga de ella, la letra A aparecería una vez en la combinación de 8 letras. Si hubiera tres puentes que condujeran a la zona, entonces la letra A aparecería dos veces. Pero como llegan cinco puentes, en este caso, A debe aparecer tres veces en esa sucesión. Similarmente, B estaría dos veces; al igual que D y C. Pero entonces, ya tendríamos nueve letras en la sucesión, cuando para ser la ruta posible únicamente debería haber ocho. Euler dedujo entonces que no se podía realizar la travesía requerida a través de los siete puentes de Königsberg.

Sin embargo, Euler no se contentó sólo con solucionar esta situación concreta, sino que se dedicó por completo al estudio del problema en general, obteniendo una solución que servía también para cualquier número de puentes.

Reglas para cruzar todos los puentes una sola vez:

- Si hay más de dos regiones a las que conducen un número impar de puentes, la ruta no será posible.

- Si sólo hay dos regiones a las que llega un número impar de puentes, la ruta se podrá realizar, comenzando en una de esas regiones.

- Si no hay regiones a las que conduzcan un número impar de puentes, la ruta pedida se podrá realizar, comenzando en cualquier punto.

Fuente: Revista SUMA, n.º 45, febrero 2004.

Icono IDevice Importante

La Teoría de Grafos permite la resolución de problemas relativos a campos tan separados como puedan ser la lingüística, la investigación operativa, la electricidad, la genética, la sociología, etc.

Un grafo consiste en un conjunto finito de vértices (puntos) y un conjunto finito de aristas (líneas) entre ellos.


Icono IDevice Para saber más

En un grafo, dos vértices se dicen adyacentes si ambos son extremos de una arista.

Toda arista es incidente con sus vértices extremos y dos aristas se dicen incidentes si ambas comparten un vértice común.

Se denomina valencia (o grado) de un vértice al número de vértices adyacentes con él o bien al número de aristas incidentes con él. Por convenio, un vértice no se considera adyacente consigo mismo y los vértices de valencia 0 se denominan vértices aislados.

Un camino en un grafo es una sucesión consecutiva de vértices y aristas del grafo, comenzando por un vértice, del tipo v1, e1, v2, e2, ..., vr-1, er, de tal manera que cada arista ei una los vértices vi-1 y vi.

Un camino euleriano sobre un grafo contiene cada arista del grafo una y sólo una vez.

Euler probó que el grafo de Königsberg no posee un camino eureliano.


Icono IDevice Curiosidad

Como curiosidad, aquí tenéis los nombres de los puentes.

 

Mapa con los nombres de los puentes

El Puente del Tendero (Shopkeeper Bridge), el Puente del Herrero (Blacksmith Bridge), el Puente de Madera (Wooden Bridge), el Puente de Miel (Honey Bridgel), el Puente Verde (Green Bridge), el Puente de los Menudillos o de los Despojos (Guts Bridge, o Giblets Bridge) y el Puente Alto (High Bridge).

Sólo cuatro de los puentes originales de Konigsberg en 1735 sobrevivieron a la segunda guerra mundial. Los de Blacksmith y Guts fueron destruidos durante la guerra, los de Shopkeeper y Green, fueron reconstruidos por los rusos, que los sustituyeron por la carretera de Leninsky Prospekt y el de Honey fue reconstruido por los alemanes en 1935, por lo que solo los puentes de Wooden y High se conservan actualmente indemnes.

 


Icono de iDevice AV - Reflexión

En 1875 los alemanes construyeron un nuevo puente en la ciudad de Königsberg, situado entre las zonas B y C.

¿Es posible ahora planificar un paseo tal que se crucen los ocho puentes sin pasar por ninguno más de una vez?

 

Dibuja el grafo asociado para que te resulte más fácil resolver el problema.

Esta unidad interactiva requiere la máquina virtual de Java J2RE.
Podemos empezar a pensar si se puede realizar el paseo trabajando directamente sobre la escena o podemos ser más sistemáticos realizando el grafo asociado y estudiando dicho grafo.
Icono de iDevice AV - Reflexión
Sobre la dársena del Guadalquivir hay 9 puentes.
- Puente del Alamillo.
- Puente de la Barqueta.
- Pasarela de la Cartuja.
- Puente del Cristo de la Expiración.
- Puente de Isabel II, también conocido como puente de Triana.
- Puente de San Telmo.
- Puente de los Remedios.
- Puente de las Delicias
- Puente del V Centenario.
Dibuja el grafo asociado y comprueba si se puede dar un paseo por todos los puentes pasando solo una vez por cada uno de ellos.


Ver Puentes de Sevilla en un mapa más grande
Icono IDevice Galería de imágenes
Muestra Imagen Puente de la Barqueta
Puente de la Barqueta
Muestra Imagen Puente del Cachorro
Puente del Cachorro
Muestra Imagen Pasarela de la Cartuja
Pasarela de la Cartuja
Muestra Imagen Puente del Alamillo
Puente del Alamillo