Problema de los Siete Puentes de Königsberg
El problema de los puentes de Königsberg, también llamado Problema de los siete puentes de Königsberg es un célebre problema matemático, resuelto por Leonard Euler en 1735 y cuya resolución dio origen a la teoría de los grafos. Su nombre se debe a Königsberg, la ciudad de Prusia Oriental y luego de Alemania que desde 1945 se convertiría en la ciudad rusa de Kaliningrado.
Esta ciudad es atravesada por el río Pregel, el cual se bifurca para rodear con sus brazos a la isla Kneiphof dividiendo el terreno en cuatro regiones distintas, las que entonces estaban unidas por siete puentes llamados Puente del herrero, Puente conector, Puente verde, Puente del mercado, Puente de madera, Puente alto y Puente de la miel. el problema fue formulado en el siglo XVIII y consistía en encontrar un recorrido para cruzar a pie toda la ciudad, pasando solo una vez por cada uno de lo puentes y regresando al mismo punto de inicio.
La teoría de los grafos es un campo de estudio de las matemáticas y las ciencias de la computación que estudia las propiedades de los grafos, estructuras que constan de dos partes , el conjunto de vértices, nodos o puntos y el conjunto de aristas, líneas o lados que pueden ser orientados o no.
La teoría de los grafos es una rama las matemáticas discretas (área de las matemáticas encargadas del estudio de los conjuntos discretos, finitos o infinitos numerables) y de las matemáticas aplicadas y es un tratado que usa diferentes conceptos de diversas áreas, como combinatoria, álgebra, probabilidad, geometría de polígonos, aritmética y topografía. Actualmente ha tenido mayor preponderancia en el campo de la informática, las ciencias de la computación y telecomunicaciones.
Leonard Euler llegó a Prusia en 1741, a la edad de 34 años, donde vivió hasta 1766, para luego regresar a San Petersburgo. Durante esos años trabajó en la Academia Prusiana de las Ciencias donde desarrolló una prolífica carrera como investigador. Fue contemporáneo de varios otros famosos matemáticos y pensadores procedentes de aquella ciudad, tales como Immanuel Kant, Johann Georg Hamann y Christina Goldbach.
Es en este ambiente y por estos años en que surge la formulación del problema de los puentes, propagándose en forma de juego y de trivia matemática entre los intelectuales de la época.
El problema consistía en responder a la siguiente pregunta: Dado el mapa de Königsberg con el río Pregel dividiendo el plano en siete 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?
La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todas los posibles recorridos existentes. Sin embargo, Euler, en 1736, 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 de Kö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 una lí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 por todas las líneas por única vez, y regresar al mismo punto de partida.
Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible necesariamente han de estar conectados en un número par de líneas. 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 significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados con un número impar de líneas. Sin embargo, el requisito adicional del problema sostiene que el punto inicial debe ser igual al del final , por lo que no podría existir ningún punto conectado con un número impar de líneas.
Esta abstracción del problema ideada por Euler dio pie a la primera noción de grafo, un tipo de estructura de datos utilizada ampliamente en matemática discreta y en ciencias de la computación.
En la teoría de los grafos existe un concepto llamado ciclo euleriano, llamado así en honor a Leonard Euler, que represeta cualquier camino dentro de un grafo particular, capaz de recorrer todas las aristas una única vez, regresando finalmente al mismo vértice original.
Por otra parte la publicación de Euler es la primera que hace alusión a una geometría en que solo interesan las propiedades estructurales de los objetos, y no sus medidas, como tradicionalmente se hace. El matemático llama a esta nueva manera de ver los objetos geométricos geometricam situs, término que hoy en día se suele traducir como topografía, área actual de la matemática cuyo origen directo puede situarse ehn la resolución de este problema.
Dos de los siete puentes originales fueron destruidos durante la Segunda Guerra Mundial. Otros dos fueron posteriormente demolidos y reemplazados por carreteras modernas. Los tres puentes restantes aun permanecen en pie, aunque solo dos de ellos desde la época de Euler, pues uno fue reconstruido en 1935.
Por lo tanto, en la actualidad, solo existen cinco puentes de Kaliningrado, disfribuidos de tal manera que ahora es posible definir un camino euleriano, es decir, una ruta que comienza en una isla y termina en otra, pero no todavía un ciclo euleriano, es decir, que la ruta comience y termine en el mismo lugar, lo cual era necesario para cumplir con las condiciones iniciales del problema.
Es en este ambiente y por estos años en que surge la formulación del problema de los puentes, propagándose en forma de juego y de trivia matemática entre los intelectuales de la época.
El problema consistía en responder a la siguiente pregunta: Dado el mapa de Königsberg con el río Pregel dividiendo el plano en siete 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?
La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todas los posibles recorridos existentes. Sin embargo, Euler, en 1736, 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 de Kö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 una lí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 por todas las líneas por única vez, y regresar al mismo punto de partida.
Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible necesariamente han de estar conectados en un número par de líneas. 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 significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados con un número impar de líneas. Sin embargo, el requisito adicional del problema sostiene que el punto inicial debe ser igual al del final , por lo que no podría existir ningún punto conectado con un número impar de líneas.
Esta abstracción del problema ideada por Euler dio pie a la primera noción de grafo, un tipo de estructura de datos utilizada ampliamente en matemática discreta y en ciencias de la computación.
En la teoría de los grafos existe un concepto llamado ciclo euleriano, llamado así en honor a Leonard Euler, que represeta cualquier camino dentro de un grafo particular, capaz de recorrer todas las aristas una única vez, regresando finalmente al mismo vértice original.
Por otra parte la publicación de Euler es la primera que hace alusión a una geometría en que solo interesan las propiedades estructurales de los objetos, y no sus medidas, como tradicionalmente se hace. El matemático llama a esta nueva manera de ver los objetos geométricos geometricam situs, término que hoy en día se suele traducir como topografía, área actual de la matemática cuyo origen directo puede situarse ehn la resolución de este problema.
Dos de los siete puentes originales fueron destruidos durante la Segunda Guerra Mundial. Otros dos fueron posteriormente demolidos y reemplazados por carreteras modernas. Los tres puentes restantes aun permanecen en pie, aunque solo dos de ellos desde la época de Euler, pues uno fue reconstruido en 1935.
Por lo tanto, en la actualidad, solo existen cinco puentes de Kaliningrado, disfribuidos de tal manera que ahora es posible definir un camino euleriano, es decir, una ruta que comienza en una isla y termina en otra, pero no todavía un ciclo euleriano, es decir, que la ruta comience y termine en el mismo lugar, lo cual era necesario para cumplir con las condiciones iniciales del problema.
Comentarios
Publicar un comentario