Los puentes de Königsberg

Se dice que el conocido problema de los puentes de Königsberg se convirtió en un dolor de cabeza para todo aquél que intentaba resolverlo, hasta que llegó el matemático Leonhard Euler. Como en muchos otros problemas en la vida, el quid de la cuestión era abordarlo desde la más rigurosa matemática. En este caso, la teoría de grafos (es más, la solución matemática que dio Euler al problema se considera como el origen histórico de esta rama de las Matemáticas).

Dicho todo esto, enunciemos el problema. En el siglo XVIII, la antigua ciudad de Königsberg en la Prusia oriental estaba bañada por el río Pregel (actuales Kaliningrado y río Pregolya en Rusia), que dividía a la ciudad en cuatro zonas, las cuales estaban conectadas por siete puentes como se ve en la figura.

Ciudad de Könisberg en la época de Euler.

Pero aún no hemos dicho en qué consiste el problema. Se pretendía encontrar una ruta en la ciudad que recorriese los siete puentes, cruzando cada uno de ellos una sola vez, terminando en el punto de partida. A priori, parece un reto tedioso pero factible, nada más lejos de la realidad. Muchos intentaron encontrar una solución sin tener éxito, por lo que empezó a pensarse que el problema no tenía solución, hasta que llegó Euler y demostró matemáticamente que, en efecto, el problema no tenía solución.

Para llegar a este resultado, Euler desarrolló una teoría llamada teoría de grafos. La idea de grafo es bastante sencilla, consiste en una pareja formada por un conjunto de puntos llamados vértices y otro conjunto formado por parejas de estos vértices llamadas aristas. En la figura podemos ver la representación gráfica de un ejemplo:

Grafo de vértices 'a', 'b', 'c' y 'd' y de aristas las líneas que los unen ('ab', 'bd', 'dc', 'ca', 'ad' y 'bc').

En nuestro problema, los vértices serán las zonas en las que queda dividida la ciudad (que son cuatro) y las aristas los puentes que las unen. De esta forma, obtendríamos un grafo que se puede representar así:

Los vértices 'A', 'B', 'C' y 'D' representan las cuatro zonas y las aristas los puentes.

Una vez traducido el problema a un grafo, basta aplicar los resultados de la teoría de grafos. Un tipo particular de grafos son llamados grafos eulerianos (en referencia a Euler y este problema), que son aquellos grafos en los que se puede encontrar un "recorrido" (no vamos a dar todas las definiciones matemáticas, nos conformamos con nuestra intuición, ¡el que quiera más detalles que deje un comentario!) que contenga todas las aristas del grafo (en nuestro caso, todos los puentes) apareciendo cada una de ellas una sola vez, y terminando en el mismo vértice en el que comienza.

El problema queda reducido, entonces, a si nuestro grafo es euleriano o no. Pero esto es muy sencillo echando mano de la teoría de grafos, en la que un resultado (probado por Euler) dice que si un grafo es euleriano, entonces todo vértice de ese grafo tiene un número par de aristas que "pasan" por él. Puesto que en nuestro grafo esto no se cumple (por ejemplo, el vértice 'D' tiene 3 aristas), no es euleriano, demostrando así que el problema de los puentes de Könisgberg no tiene solución.

Una vez más, las Matemáticas nos muestran su potencial y su gran utilidad (a pesar de lo que piensan la mayoría de los escolares XD). Si te ha gustado, ¡deja un comentario!

¡Sigue a nuestra página de facebook!