entrar registro

Problema de los 7 puentes de Konisberg. Planteamiento e imposibilidad de resolución

369 visitas
|
votos: 17 · 0
|
karma: 153
|

El señor que sale en la imagen (abajo a la derecha) es Leonhard Euler. Se trata del principal matemático del siglo XVIII y uno de los más grandes y prolíficos de todos los tiempos, muy conocido por el número de Euler (e), número que aparece en muchas fórmulas de cálculo y física. A él también se le deben la forma actual de escribir las funciones f(x), las funciones trigonométricas (sen x y cos x, por ejemplo) y su relación con los números complejos a través de la fórmula que lleva su nombre. Pero este artículo no trata de las investigaciones de Euler sino de la resolución que dio a un problema célebre en aquella época.

El problema dice así: 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? (ver mapa de Königsberg en la imagen)

Euler resolvió este problema en 1736 y lo más importante no es la solución en sí, que podía ser abordado por fuerza bruta, sino el método que utilizó: simplificó el mapa de la ciudad convirtiéndolo en cuatro puntos que son las cuatro regiones en las que el río divide la ciudad y trazó líneas uniendo esos puntos de forma equivalente a como los puentes unen las regiones de la ciudad. En este momento del texto es conveniente que mires el mapa de la ciudad y el diagrama de puntos y líneas de la imagen del encabezado y pienses en su equivalencia. (pista: el punto de la izquierda equivale a la isla central)

Una vez simplificado el mapa, estudió las líneas que salen y llegan a los puntos. Consideró que para cumplir las condiciones del problema debía empezar y terminar en un mismo punto, y el resto de puntos debían ser de paso intermedio. Pues bien: a estos puntos de paso intermedios necesariamente deben llegarles una cantidad par de líneas. Si no fuera así, se daría la situación de que al llegar a ese punto no podríamos salir de él por un camino diferente.

¿Y que pasa con el punto de inicio y de final? Pues que esos podrían tener una cantidad impar de líneas (salir de un sitio y no volver a pasar por ahí, o terminar en un sitio sin tener que salir de ahí), pero como el problema exige que comience y termine en el mismo sitio también han de ser pares porque hay que volver al punto de partida por un camino diferente.

Euler concluyó que no es posible recorrer el mapa como pide el problema porque el diagrama en el que él simplificó el problema tiene todos los puntos con un número impar de líneas (tres puntos tienen tres líneas y el otro tiene cinco). La forma de abordar este problema dio lugar a la teoría de grafos tan utilizada en programación. Al diagrama de puntos y líneas se le llama grafo, los puntos son vértices del grafo y las líneas se denominan aristas.

Hoy en día Königsberg se llama Kaliningrado, ya no está en Prusia sino en Rusia. En la Segunda Guerra Mundial se destruyeron dos puentes, posteriormente se remodelaron otros dos, de modo que en lugar de los siete puentes del problema original hoy en día solo quedan cinco. Esto ha cambiado la fisonomía de la ciudad y el problema hoy en día sigue siendo irresoluble con la condición de empezar y terminar en el mismo sitio, pero sí se puede cumplir si empiezas en un sitio y permites terminar en otro.

La estructura de este artículo, las imágenes y su contenido está sacado de la entrada de la wikipedia "Problema de los puentes de Königsberg" es.wikipedia.org/wiki/Problema_de_los_puentes_de_Königsberg

comentarios (8)
rusadir
¿Alguien se atreve a resolver el problema ahora, con 5 puentes y sin la condición de empezar y terminar en el mismo sitio?

media
3    k 72
omoloc
#1 yo veo 6 puentes...

Esto lo di en la carrera.

Por cierto, si eres matemático, tengo una propuesta matemática para reparto proporcional (caso típico de reparto de escaños en una elecciones) que es muy obvia, pero no he visto desarrollada en ningún lado, por si te interesa
3    k 79
rusadir
#3 Hola,

La verdad es que nunca me he dedicado a eso, pero si lo pasas le puedo echar un vistazo. :-)
1    k 33
omoloc
#6 Nadie se dedica a eso. Se estudió hace 200 años y ahí se quedó

Hecho. Escribo aquí un artículo sobre el tema y me dices qué te parece. Gracias!
1    k 34
macarty
#4 macarty
 *
#1 el algoritmo minimizacion de grafos creo que sirve para eso. Está en el tipo de problemas NP completos, trasladandolo a una matriz y tratando de reducir el grafo, pero creo que se tiene que hacer por fuerza bruta
1    k 35
macarty
#4 Lo sabía, este fue uno de los ejemplos de clase que me tocó resolver alguna vez

aprendiendomatematicas.com/los-puentes-de-konigsberg/

cc: @rusadir
1    k 35
function
Me flipa estos genios matemáticos los grandes avances que lograron sin ordenadores, siquiera.
4    k 99
suscripciones por RSS
ayuda
+mediatize
estadísticas
mediatize
mediatize