Problema de los puentes de Königsberg
Los Siete Puentes de Königsberg es un problema matemático históricamente famoso. Leonhard Euler lo resolvió en 1735. Esto condujo al inicio de la teoría de grafos. Esto condujo al desarrollo de la topología.
La ciudad de Königsberg, en Prusia (actualmente Kaliningrado, Rusia), estaba situada a ambos lados del río Pregel. Incluía dos grandes islas que estaban conectadas entre sí y con el continente por siete puentes.
El problema era encontrar una forma de atravesar la ciudad cruzando cada puente una y sólo una vez. No se podía llegar a las islas por ninguna otra ruta que no fueran los puentes. Cada puente debía ser cruzado completamente cada vez. No es necesario que el paseo comience y termine en el mismo punto. Euler demostró que el problema no tiene solución.
Mapa de Königsberg en la época de Euler que muestra el trazado real de los siete puentes, destacando el río Pregel y los puentes
Análisis de Euler
En primer lugar, Euler señaló que la elección de la ruta dentro de cada masa de tierra no importa. La única propiedad importante de una ruta es el orden en que se cruzan los puentes. Así, cambió el problema a términos abstractos. Esto sentó las bases de la teoría de los grafos. Eliminó todas las características excepto la lista de masas de tierra y los puentes que las conectan. En el lenguaje de la teoría de grafos, sustituyó cada masa de tierra por un "vértice" o nodo abstracto. Luego sustituyó cada puente por una conexión abstracta, una "arista". Una arista (carretera) registraba qué dos vértices (masas de tierra) estaban conectados. De este modo, formó un gráfico.
→ → 
El gráfico dibujado es una imagen abstracta del problema. Por lo tanto, las aristas pueden unirse de cualquier manera. Sólo es importante si dos puntos están conectados o no. Cambiar la imagen del gráfico no cambia el gráfico en sí.
A continuación, Euler observó que (excepto en los puntos finales del paseo), siempre que se entra en un vértice por un puente, se sale del mismo por un puente. En cualquier recorrido del grafo, el número de veces que se entra en un vértice es igual al número de veces que se sale de él. Si cada puente se ha cruzado exactamente una vez, se deduce que, para cada masa de tierra (excepto las elegidas para el inicio y el final), el número de puentes que tocan esa masa de tierra debe ser par. Esto es así porque si hay n puentes, se cruza exactamente 2n veces. Sin embargo, las cuatro masas de tierra del problema original están tocadas por un número impar de puentes (una está tocada por 5 puentes y las otras tres por 3). Hay como máximo dos masas que pueden ser los puntos finales de un paseo. Por lo tanto, la proposición de un paseo que atraviesa cada puente una vez conduce a una contradicción.
En lenguaje moderno, Euler demuestra que el hecho de que un paseo por un grafo cruzando cada arista una vez sea posible o no depende de los grados de los nodos. El grado de un nodo es el número de aristas que lo tocan. Euler muestra que una condición necesaria para el paseo es que el grafo esté conectado y tenga exactamente cero o dos nodos de grado impar. Este resultado enunciado por Euler fue demostrado posteriormente por Carl Hierholzer. Este paseo se denomina ahora camino euleriano o paseo de Euler. Si hay nodos de grado impar, cualquier camino euleriano comenzará en uno de ellos y terminará en el otro. Como el grafo que representa la Königsberg histórica tiene cuatro nodos de grado impar, no puede tener un camino euleriano.
El trabajo de Euler fue presentado a la Academia de San Petersburgo el 26 de agosto de 1735. Se publicó como Solutio problematis ad geometriam situs pertinentis (La solución de un problema relativo a la geometría de la posición) en la revista Commentarii academiae scientiarum Petropolitanae en 1741. Está disponible en inglés en The World of Mathematics.
Estado actual de los puentes
En la historia de las matemáticas, la solución de Euler al problema del puente de Königsberg se considera el primer teorema de la teoría de grafos. La Teoría de Grafos es una materia que ahora se considera generalmente como una rama de la combinatoria.
[
{[89192-68750]}]
Dos de los siete puentes originales fueron destruidos durante el bombardeo de Königsberg en la Segunda Guerra Mundial. Otros dos fueron demolidos posteriormente. Fueron sustituidos por una moderna autopista. Los otros tres puentes permanecen, aunque sólo dos de ellos son de la época de Euler (uno fue reconstruido en 1935). Así, en el año 2000, había cinco puentes en Kaliningrado.
En términos de teoría de grafos, dos de los nodos tienen ahora grado 2, y los otros dos tienen grado 3. Por lo tanto, un camino euleriano es ahora posible, pero como debe comenzar en una isla y terminar en la otra, es poco práctico para los turistas.
Páginas relacionadas
- Juego de Icosian
- Trayectoria hamiltoniana
- Agua, gas y electricidad
- Problema del viajante de comercio
Preguntas y respuestas
P: ¿En qué consiste el problema de los Siete Puentes de Königsberg?
R: El de los Siete Puentes de Königsberg es un famoso problema matemático que consiste en encontrar la forma de atravesar la ciudad cruzando cada uno de sus siete puentes una y sólo una vez.
P: ¿Quién resolvió el problema de los Siete Puentes de Königsberg?
R: Leonhard Euler resolvió el problema de los Siete Puentes de Königsberg en 1735.
P: ¿A qué condujo la solución del problema de los Siete Puentes de Königsberg?
R: La solución del problema de los Siete Puentes de Königsberg condujo al inicio de la teoría de grafos, que a su vez condujo al desarrollo de la topología.
P: ¿Dónde se encuentra Königsberg?
R: Königsberg está situada en Prusia, que ahora forma parte de Kaliningrado, Rusia.
P: ¿Cuál era el trazado de Königsberg?
R: Königsberg estaba trazada a ambos lados del río Pregel e incluía dos grandes islas que estaban conectadas entre sí y con el continente por siete puentes.
P: ¿Cuáles eran los requisitos para resolver el problema de los siete puentes de Königsberg?
R: El problema requería encontrar una forma de atravesar la ciudad cruzando cada puente una y sólo una vez, y cruzando cada puente por completo cada vez. No se podía llegar a las islas por otra ruta que no fueran los puentes, y no era necesario que el paseo empezara y terminara en el mismo punto.
P: ¿Demostró Euler que el problema de los siete puentes de Königsberg tiene solución?
R: No, Euler demostró que el problema de los Siete Puentes de Königsberg no tiene solución.
