domingo, 11 de enero de 2009

Problema de los puentes de Königsberg

Ví un documental sobre la problemática y la solución que se presentaba en Prusia. Aquí les comparto lo que encontré en Wikipedia.

El problema de los siete puentes de Königsberg (Prusia oriental en el siglo XVIII -ciudad natal de Kant- y actualmente, Kaliningrado, en la óblast rusa de Kaliningrado) es un célebre problema matemático que fue resuelto por Leonhard Euler en 1736 y dio origen a la Teoría de los grafos.

Consiste en lo siguiente:

Dos islas en el río Pregel que cruza Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?

Imagen:puentes_Konigsberg.jpg

Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo terminando en el punto de partida sin repetir las líneas?

Imagen:puentes_Kronigsberg_grafo.jpg

Euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto regresando al punto de partida por caminos distintos en todo momento). En teoría de los grafos esta idea se corresponde con la posibilidad de encontrar un Ciclo Euleriano en un grafo.

Mapa de Königsberg

Image:Konigsberg bridges.png

Este mapa de Königsberg de la época de Euler muestra dónde se encontraban los siete puentes (en verde claro) y las ramas del río (en azul cielo).

1 comentarios:

popis dijo...

Hola como va?, muchas gracias por tu comentario, este blog me parece interesante también, jeje, justamente hoy acabo de juntarme con amigos de la facu a estudiar matemáticas, la verdad no me va, lo mío es otra cosa, pero sé es absolutamente necesario asique otra no queda; bueno mañana empezaremos a estudiar Grafos, y esta teoría acerca de los puentes de Königsberg va incluída también, asique leer este post me refresco la memoria, se agradece =).

Bueno que estés bien, y también chusmearé tu blog.

Chau!.