Este problema fue resuelto por Leonard Euler, dando origen a
la teoría de grafos.
Königsberg es el antiguo
nombre que recibía la ciudad de Kaliningrado, cuyo mapa se ve en la imagen. El
enunciado del problema dice lo siguiente:
“Dado el mapa de Königsberg, con el río Pregolya 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 sólo una vez cada uno, y regresando al mismo punto de partida?”
Solución
En 1736, Leonard Euler presenta la solución: esta no existe.
Para demostrarlo, primero realizó una abstracción del mapa,
como se muestra en la siguiente imagen:
El matemático determinó que los puntos intermedios de cualquier recorrido posible necesariamente han de estar conectados a un número par de líneas, ya
que si llegamos a uno desde alguna línea, entonces el único modo de salir de
ese punto es por una línea diferente. En este
caso, el punto inicial y el final coinciden, por lo que también deberían
tener un número par de líneas.
Como en el mapa de Königsberg todos los puntos están unidos
a una cantidad impar de puentes, se deduce que no es posible cumplir con el
enunciado.
La solución al problema dio pie a la primera noción de
grafo, un término usado ampliamente en matemática discreta y en ciencias de la
computación.
No hay comentarios.:
Publicar un comentario