TRAYECTORIAS DE EULER - El problema de los puentes de Königsberg

En honor de Leonhard Euler, se llama una trayectoria de Euler a un camino que recorre todas las aristas de una gráfica conexa.

El problema de los puentes de Königsberg

Königsberg era un puerto de la antigua Alemania (actualmente pertenece a Rusia y se llama Kaliningrado), situado en la costa sur del mar Báltico, la segunda capital de Prusia, está dividido por el río Pregel en cuatro zonas, incluyendo la isla de Kneiphof. Hay siete puentes que conectan las diferentes partes de la ciudad y hay un acertijo acerca de ellos que intrigó grandemente a los ciudadanos de Königsberg hace unos doscientos años.

Dar un paseo por los puentes ha sido siempre un entretenimiento para recreación de los jóvenes. Según los viejos relatos, de una manera o de otra se presentó la pregunta de cuánto llevaría recorrer los puentes. Esto condujo a la sorprendente afirmación de que un recorrido completo de todos los puentes sin pasar más de una vez por ninguno de ellos era imposible.

Es un hecho histórico que un comité de jóvenes visitó a Leonard Euler, el matemático, en 1735, para pedirle que resolviera el conflictivo tema. Un año más tarde, Euler presentó un voluminoso informe a la Academia de Ciencias de San Petersburgo. Allí afirmaba haber demostrado la imposibilidad de resolver el problema. Esta conclusión aparece en el informe de la Academia, 1741, Vol. 8, y ha sido publicada en inglés y francés por renombrados matemáticos, ya que se ocupa del principio aplicándolo a cualquier número de puentes.

El profesor W. Rouse Ball, de Trinity College, discute la antigüedad y los méritos del problema en su gran obra Mathematical Recreations, pero se equivoca al adjudicar su origen a Euler en 1736 y hace la notable afirmación de que había y aún hay, según Baedecker, solamente siete puentes. Los registros más antiguos se refieren a ocho y el mapa presenta un acertado esquema de Baedecker, quien serefiere especialmente a los ocho puentes.

La cuestión de regresar al punto de partida no forma parte en absoluto del problema. Sólo se trata de demostrar si es posible partir de cierto sitio de la ciudad y llegar a otro sitio pasando una sola vez por todos los puentes. El problema es decir de cuántas maneras es posible hacerlo y cuál es la ruta más corta.

En el año 1935 se construyó un nuevo puente, uniendo las áreas de tierra B y C. Supongamos que cada vez que se cruza un puente de la ciudad de Königsberg se tienen que pagar $1000 y que se requiere hacer un recorrido cruzando cada puente por lo menos una vez.

i. ¿Existe una caminata?

ii. Describir el recorrido más barato que comienza y termina en el área de tierra B.

iii. Describir el recorrido más barato si se permite empezar y terminar en áreas de tierra diferentes.

Solución

i. Si existe una caminata; la gráfica que se obtiene posee exactamente dos vértices de grado impar, los vértices A y D. Una trayectoria de Euler que comienza en A y finaliza en D es A, B, A, C, A,D, B, C, D.

ii. El recorrido más barato cuesta $9000; de acuerdo con la gráfica del problema, un posible recorrido que empieza y termina en el área de tierra B es B, A, C, D, C, A, D, B, A, B. En esterecorrido, tanto el puente CD como alguno de los puentes AB son cruzados dos veces.

iii. El recorrido más barato cuesta $8000. Un posible recorrido que comienza en C y finaliza en A es B, A, C, D, C, A, D, B, A; en este recorrido el puente CD se cruza dos veces.

Ver en el minuto 3:32 by TECtv La Señal de la Ciencia