El problema de los puentes de Königsberg

Un paseo por Königsberg

El problema, de carácter turístico-recreativo y relativo a la cuidad de Königsberg (actual Kaliningrado) era bien conocido, decía:

“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?”.

mapakonigs

Dicho problema puede resolverse utilizando “fuerza bruta” y probando todos los recorridos posibles y viendo que exactamente no es posible realizar semejante paseo. Sin embargo, la solución dada por Leonhard Euler en 1736, fue la primera piedra de lo que en la actualidad se conoce como teoría de grafos.

Teoría de grafos. Nociones básicas

Euler simplificó el problema numerando los puentes y denotando por letras cada una de las regiones urbanas:

mapa2

El siguiente paso que dio Euler fue eliminar toda la geografía propia de la cuidad, es decir, simplificar el problema aún más, reduciendo este a puntos (regiones) y aristas (puentes):

grafociudad

Euler determinó que era imposible completar el recorrido demandado por el problema, dado que para ello el número líneas por cada punto debía de ser par, y no lo era. Esta conclusión es lógica ya que si llegamos a un punto desde una línea, debemos abandonarlo por una línea diferente. Asimismo el problema no impone ninguna restricción sobre pasar varias veces por la misma región, solo dice que no se puede pasar por el mismo puente dos veces. El problema también impone la condición de que el punto inicial y final debe de ser el mismo.

Así que el paseo propuesto por el problema es imposible de realizar. Además, lamentablemente los puentes fueron destruidos durante la Segunda Guerra Mundial.

Lo que Euler había dibujado es lo que más tarde se conocería como teoría de grafos.

Tres familias y tres suministros

El siguiente problema es famosísimo y estoy seguro de que muchos habéis oído hablar de el. Básicamente el problema propone que tratemos de conectar en el plano tres casas con tres suministros (luz, agua y gas) sin que ninguna de las líneas de conexión se crucen. Un esquema del problema sería el siguiente:

grafocasas1

Inmediatamente nos percatamos de que este es un problema de teoría de grafos, solo que en esta ocasión tenemos que encontrar la forma de conseguir conectar cada una de las tres casas con los tres suministros sin que ninguna línea se cruce (en lugar de buscar un recorrido). Tras pelearnos un rato con dicho problema, nos damos cuenta de que no tiene solución (en el plano, en el espacio es evidente que sí) puesto que acabamos siempre llegando a un esquema equivalente al mostrado en la siguiente figura:

grafocasas2

En este grafo tenemos todas nuestras conexiones hechas salvo una. El problema es que realizar esta última conexión requiere incumplir la parte del enunciado que dice que ningún suministro puede cruzarse. La pregunta ahora sería, ¿Por que no tiene solución este problema?. Dibujemos el mismo grafo pero de manera más simple. El siguiente grafo es equivalente:

grafocasas3

Como podemos ver la única conexión que falta por realizar es la casa 2 con el suministro de gas. Y esta es imposible de realizar ya que según el Teorema de Jordan: “si una curva continua, simple y plana divide el plano en dos regiones (interior y exterior), cualquier curva continua que una un punto de dentro y otro de fuera cortará en al menos un punto a la curva dada”. En este caso la curva que une la casa 1 con el suministro de agua es la curva divisoria, y como se observa en la figura anterior, la casa 2 queda en el exterior y el suministro de gas en el interior.

Muy interesante, pero… ¿y esto para que vale?

La teoría de grafos tiene aplicaciones en muchos y muy diversos campos más allá de la matemática recreativa. Sin ir más lejos Internet. La forma de conexión de varios equipos puede ser mediante diferentes tipos de grafo (en estrella, ciclo, árbol…), esto se conoce como topología de redes. En química se utiliza ampliamente para representar de manera simple los enlaces moleculares. Dentro de la física encuentra aplicaciones en la electrónica y en los circuitos. En arquitectura se utiliza para analizar las distribuciones y conexiones entre las habitaciones. Los mapas de metro también utilizan los grafos para mostrar de forma simplificada una gran cantidad de información sobre rutas y conexiones entre las diferentes lineas. A la hora de entender el pensamiento humano y trabajar con inteligencia artificial, la teoría de grafos ha sido utilizada para construir lo que se conoce como redes neuronales artificiales. El Atomium de Bruselas está basado en el grafo de la molécula de hierro. Y podríamos seguir…

Sin duda las aplicaciones de la teoría de grafos son infinitas, bien es cierto que las matemáticas recreativas pueden ser la parte más atractiva, por eso para terminar este artículo, un desafío para el lector, para que pueda sentirse como el gran Leonhard Euler paseando por Königsberg.

¿Puedes recorrer el siguiente grafo pasando por todas las aristas y haciéndolo una sola vez?

problemacircunf

Un comentario en “El problema de los puentes de Königsberg

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 )

Google+ photo

Estás comentando usando tu cuenta de Google+. 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 )

Conectando a %s