problema de los puentes de königsberg
DESCRIPTION
IOTRANSCRIPT
Problema de los puentes de KönigsbergCoordenadas: 54°42′12″N 20°30′56″E (mapa)
Mapa de Königsberg en la época de Leonhard Euler , que muestra dónde se encontraban los siete puentes (en verde claro) y las ramas del río
(en celeste).
El problema de los puentes de Königsberg, también llamado más específicamente problema de los
siete puentes de Königsberg, es un célebre problema matemático, resuelto por Leonhard
Euler en 1736 y cuya resolución dio origen a la teoría de grafos.1 Su nombre se debe a Königsberg, el
antiguo nombre que recibía la ciudad rusa de Kaliningrado, que durante el siglo XVIII formaba parte
de Prusia Oriental, como uno de los ducados del Reino de Prusia.
Esta ciudad es atravesada por el río Pregolya, el cual se bifurca para rodear con sus brazos a la
islaKneiphof,2 dividiendo el terreno en cuatro regiones distintas, las que entonces estaban unidas
mediante siete puentes llamados Puente del herrero, Puente conector, Puente verde, Puente del
mercado, Puente de madera, Puente alto y Puente de la miel.3 El problema fue formulado en el siglo
XVIII y consistía en encontrar un recorrido para cruzar a pie toda la ciudad, pasando sólo una vez por
cada uno de los puentes, y regresando al mismo punto de inicio.4
[editar]Contextualización del problema
Leonhard 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 laAcademia Prusiana de las Ciencias, donde
desarrolló una prolífica carrera como investigador.5 Euler fue contemporáneo de varios otros famosos
matemáticos y pensadores procedentes de aquella ciudad, tales como Immanuel Kant , Johann Georg
Hamann y Christian Goldbach, por lo que Königsberg fue en ese tiempo un importante epicentro
científico.
Es en este ambiente y por estos años en que surge la formulación del problema de los puentes de
Königsberg, propagándose a modo de juego y de trivia matemática entre los intelectuales de la época.
[editar]Análisis y solución del problema
Leonhard Euler (1707 - 1783), famoso matemático que resolvió el problema en 1736, dando origen a lateoría de grafos. Retrato de 1753.
El problema, formulado originalmente de manera informal, consistía en responder a la siguiente
pregunta:
Dado el mapa de Königsberg, con el río Pregolya 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 sólo 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 todos los posibles recorridos
existentes. Sin embargo, Euler en 1736 en su publicación «Solutio problematis ad geometriam situs
pertinentis»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 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
una única vez, y regrese al mismo punto de partida.
→
→ [editar]Demostración
Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible
necesariamente 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
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 dice que el punto inicial debe
ser igual al final, por lo que no podría existir más de un único punto conectado con un número impar de
líneas.nota 1
En particular, como en este diagrama los cuatro puntos poseen un número impar de líneas incidentes
(tres de ellos inciden en tres líneas, y el restante incide en cinco), entonces se concluye que es
imposible definir un camino con las características buscadas.
[editar]Repercusiones
Esta abstracción del problema ideada por Euler dio pie a la primera noción de grafo, que es un tipo
de estructura de datos utilizada ampliamente en matemática discreta y en ciencias de la computación. A
los puntos se les llaman vértices y a las líneas aristas. Al número de aristas incidentes a un vértice se le
llama el gradode dicho vértice. Específicamente, un diagrama como el de la abstracción del mapa de
Königsberg representa un multigrafo no dirigido sin bucles.
En la teoría de grafos, existe un concepto llamado ciclo euleriano, llamado así justamente en honor a
Leonhard Euler, que representa cualquier camino dentro de un grafo particular, capaz de recorrer todas
las aristas una única vez, regresando finalmente al mismo vértice original. En coloración de grafos, una
subárea de la teoría de grafos, la resolución de este problema constituye además el primer teorema de
los grafos planares.6
Por otra parte, la publicación de Euler es la primera que hace alusión a una geometría en que sólo
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 «geometriam situs»,
término que hoy se traduce como topología,2 área actual de la matemática cuyo origen directo puede
situarse en la resolución de este problema.7
[editar]El problema original en la actualidad
Puente de la Miel sobre el río Pregolya enKaliningrado.
Dos de los siete puentes originales fueron destruidos por el bombardeo de Königsberg durante
la Segunda Guerra Mundial. Otros dos fueron posteriormente demolidos y reemplazados por carreteras
modernas. Los tres puentes restantes aún permanecen en pie, aunque sólo dos de ellos desde la época
de Euler, pues uno fue reconstruido en 1935.8
Por lo tanto, en la actualidad sólo existen cinco puentes en Kaliningrado, distribuidos de tal manera que
ahora es posible definir un camino euleriano, es decir, una ruta que comienza en una isla y terminar 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.9
[editar]Véase también
Teoría de grafos
Ciclo euleriano
[editar]Referencias
1. ↑ a b Euler, Leonhard (1736). «Solutio problematis ad geometriam situs pertinentis» (en latín). Comment. Acad. Sci. U.
Petrop 8, 128-40 (Reimpreso en Opera Omnia Series Prima, Vol. 7. pp. 1-10, 1766). Consultado el 11 de abril de 2010.
2. ↑ a b Astrocosmo (2001-2002). «El Problema de los Puentes de Königsberg» (en español). Consultado el 28 de abril de
2010.
3. ↑ MathDL. «Leonard Euler's Solution to the Konigsberg Bridge Problem» (en inglés). Consultado el 11 de abril de 2010.
4. ↑ Weisstein , Eric W . «Problema de los puentes de Königsberg» (en inglés). MathWorld. Wolfram Research .
5. ↑ Dunham, William (1999). Euler: The Master of Us All. The Mathematical Association of America. pp. xxiv–xxv.
6. ↑ Alexanderson, Gerald (July 2006). «Euler and Königsberg's bridges: a historical view». Bulletin of the American
Mathematical Society.
7. ↑ Pappas, T. "Königsberg Bridge Problem & Topology." The Joy of Mathematics. San Carlos, CA: Wide World
Publ./Tetra, pp. 124-125, 1989.
8. ↑ Taylor, Peter (diciembre de 2000). Australian Mathematics Trust (ed.): «What Ever Happened to Those Bridges?».
Consultado el 12 de abril de 2010.
9. ↑ Stallmann, Matthias (julio de 2006). «The 7/5 Bridges of Koenigsberg/Kaliningrad». Consultado el 12 de abril de 2010.
[editar]Notas
1. ↑ En realidad, en estos recorridos, llamados ciclos eulerianos, no pueden existir puntos con un número impar de líneas
incidentes. Solo en el caso de los caminos eulerianos, donde se acepta que el punto inicial y el final sean distintos,
puede darse que únicamente éstos tengan un número impar de líneas incidentes. Euler sólo caracterizó formalmente los
caminos eulerianos; la caracterización formal de ciclo euleriano la hizo Carl Hierholzer más tarde, en 1873, lo que no
impide que la demostración de Euler sea general y correcta.
Fuente: Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976) (en inglés). Graph Theory 1736-1936. Oxford: Clarendon Press.
pp. 239.