No Se
Páginas: 4 (838 palabras)
Publicado: 4 de abril de 2012
Los puentes de Königsberg
Königsberg (actualmente Kaliningrado, Rusia) era una ciudad de Prusia del siglo XVIII. El problema que nos ocupa tiene como protagonista a un río, el río Pregel, quecruzaba la ciudad, a dos islas que se encontraban en el mismo y a siete puentes que comunicaban las dos partes de la ciudad con las mismas. Concretamente la situación era como se describe en la imagen( y son las dos partes de la ciudad y y las dos islas):
El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida. Antes de seguirleyendo podéis intentarlo vosotros mismos, aunque os recomiendo que no le dediquéis demasiado tiempo.
La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puederesolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos existentes. Sin embargo, Euler en 1736 en su publicación «Solutio problematis ad geometriam situspertinentis»1 demuestra una solución generalizada del problema, que puede aplicarse a cualquier territorio en que ciertos accesos estén restringidos a ciertas conexiones, tales como los puentes deKönigsberg.
Para dicha demostración, Euler recurre a una abstracción del mapa, enfocándose exclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente lo representó mediante unalínea que unía a dos puntos, cada uno de los cuales representaba una región diferente. Así el problema se reduce a decidir si existe o no un camino que comience por uno de los puntos azules, transite portodas las líneas una única vez, y regrese al mismo punto de partida.
→ →
Demostración
Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posiblenecesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto...
Königsberg (actualmente Kaliningrado, Rusia) era una ciudad de Prusia del siglo XVIII. El problema que nos ocupa tiene como protagonista a un río, el río Pregel, quecruzaba la ciudad, a dos islas que se encontraban en el mismo y a siete puentes que comunicaban las dos partes de la ciudad con las mismas. Concretamente la situación era como se describe en la imagen( y son las dos partes de la ciudad y y las dos islas):
El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida. Antes de seguirleyendo podéis intentarlo vosotros mismos, aunque os recomiendo que no le dediquéis demasiado tiempo.
La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puederesolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos existentes. Sin embargo, Euler en 1736 en su publicación «Solutio problematis ad geometriam situspertinentis»1 demuestra una solución generalizada del problema, que puede aplicarse a cualquier territorio en que ciertos accesos estén restringidos a ciertas conexiones, tales como los puentes deKönigsberg.
Para dicha demostración, Euler recurre a una abstracción del mapa, enfocándose exclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente lo representó mediante unalínea que unía a dos puntos, cada uno de los cuales representaba una región diferente. Así el problema se reduce a decidir si existe o no un camino que comience por uno de los puntos azules, transite portodas las líneas una única vez, y regrese al mismo punto de partida.
→ →
Demostración
Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posiblenecesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto...
Leer documento completo
Regístrate para leer el documento completo.