LOS PUENTES DE KÖNIGSBERG
Bloque. Taller de Matemáticas
 

EL PROBLEMA DE LOS PUENTES DE KÖNIGSBERG
Königsberg fue una populosa y rica ciudad de la Prusia Oriental. Hoy en día su nombre es Kaliningrado y pertenece a Rusia. Está situada en las orillas y en las islas del río Pregel, que en el siglo XVIII estaba atravesado por siete puentes. Es conocida por ser la cuna del filósofo I. Kant (1724-1804), pero en la historia de las Matemáticas es famosa por la disposición de sus puentes que dio lugar a un juego, precisamente en la época de Kant, que atrajo la atención de los más famosos matemáticos del momento.

El juego consiste en lo siguiente: ¿Es posible planificar un paseo tal que se crucen todos los puentes sin pasar por ninguno más de una vez?

Algunos de los habitantes de Königsberg opinaban que sí y otros que no.

Para que el lector de estas notas pueda tener su propia opinión, la escena presenta de forma esquemática la disposición de los puentes y un control que al moverlo deja un rastro. Cuando queramos empezar un "paseo" llevaremos el control al lugar de inicio, pulsamos sobre el botón <Limpiar> y ya podemos marcar un nuevo camino.

LA SOLUCIÓN DE LEONARD EULER
Leonard Euler (1707-1783), genio de las Matemáticas natural de Basilea (Suiza), dio al problema una respuesta segura: ¡No es posible planificar un paseo que recorra todos los puentes una única vez!

La investigación que realizó Euler para resolver este problema fue presentada en 1736 en la Academia de Ciencias de San Pesterbusgo. La obra de Euler puede considerarse como el comienzo de la Teoría de Grafos, que forma parte de la Topología, rama de las Matemáticas que Leibniz llamó "geometría de la posición".

Euler, para mayor claridad, sustituyó cada uno de los trozos de tierra firme por un punto y cada puente por un trazo, dando lugar a un esquema simplificado que se representa en la figura adjunta. Así, la isla está representada por el punto al cual llegan cinco trazos, pues son cinco los puentes que van a ella. La figura resultante es un grafo (un grafo es un conjunto de puntos llamados "vértices o nodos" del grafo y un conjunto de lineas que los unen que se llaman "aristas o lados" del grafo).

El problema se reduce a dibujar la figura, partiendo de un punto, de un trazo, es decir, sin levantar el lápiz (boli, pluma...) del papel y sin recorrer una misma línea dos veces. A un recorrido de estas características se le llama camino euleriano.

Demostraremos que es imposible dibujar nuestra figura de un solo trazo. En efecto, a cada punto nodal hay que llegar por un lado y salir por otro distinto; esta regla sólo tiene dos excepciones que son el punto de salida, al cual no hay que llegar y el punto de llegada, del cual no hay que salir.

Por lo tanto, si un tal recorrido fuera posible, es necesario que en todos los vértices del grafo, salvo a lo más en dos, converjan dos, cuatro... aristas, es decir, converja un número par de ellas. Pero en cada uno de los nodos del grafo correspondiente a los puentes de Königsberg concurre un número impar de aristas (3, 5, 3, 3).

Por lo dicho en el párrafo anterior, si existe un camino euleriano, tenemos dos posibilidades:

  • El punto de partida y de llegada es el mismo, entonces en todos los vértices concurre un número par de aristas.
  • Los puntos de partida y de llegada son distintos, entonces hay dos vértices con número impar de aristas (el de partida y el de llegada) y todos los demás tienen un número par de aristas.

El recíproco de esta afirmación es también cierto, es decir, si ocurre alguna de las dos posibilidades anteriores, existe un camino euleriano y podríamos realizar la figura correspondiente sin levantar el lápiz del papel y sin pasar dos veces por una misma arista. Además, si todos los nodos tienen un número par de arista se puede empezar por cualquiera de ellos y se terminará, naturalmente, en el que se empezó; y si hay sólo dos con un número impar de aristas, se empieza en uno de ellos y se termina en el otro. La demostraciones formales de estas afirmaciones están fuera del alcance de estas notas.

Después de todo lo comentado se comprenderá por qué la "casita" tiene un camino euleriano y el "sobre" no

Una observación final: no es necesario realizar el grafo, éste se hizo por claridad de la exposición. Podríamos haber contado los puentes que partían de cada trozo de tierra firme y luego haber razonado como lo hizo Euler. 


OCHO PUENTES
Unos años después construyeron un puente más. ¿Es posible ahora planificar un paseo tal que se crucen los ocho puentes sin pasar por ninguno más de una vez?
La escena presenta la configuración de puentes resultante con el puente añadido. Podemos empezar a pensar si se puede realizar el paseo trabajando directamente sobre la escena o podemos ser más sistemáticos realizando el grafo asociado y estudiando dicho grafo como se ha descrito anteriormente.

OTRAS FIGURAS
Seguramente el lector conozca otros ejemplos de figuras que hay que realizar sin levantar el lápiz del papel y sin pasar dos veces por la misma línea y con las cuales pueda practicar lo aprendido. Por si no es el caso, a continuación se presentan unas cuantas.

Exponemos en la escena hasta un total de ocho figuras diferentes en las cuales hay que encontrar, si existe, un camino euleriano. Antes de empezar a buscar un camino debemos asegurarnos si tal existe. O sea, debemos aplicar todo lo que se ha expueto en los apartados anteriores.

Para pasar de una figura a otra se pulsa sobre las flechas del parámetro "Figura". ¡Suerte y a divertirse!


PASATIEMPO FINAL

Hace unos cuantos años, cuando yo estudiaba el Curso de Orientación Universitaria (el COU) circulaba entre los alumnos el pasatiempo que se verá en la escena que sigue. Se trata de cortar todos los lados de la figura que aparece con una línea continua y sin que un lado sea cortado más de una vez. No se permite pasar por un vértice y pensar que se han cortado así dos o tres lados. La imagen que hay a la derecha de la escena es un inicio del juego que espero que sirva para clarificar las reglas del mismo. Obviamente, si está colocado en esta página es porque alguna relación tendrá con todo lo que se ha expuesto hasta ahora. Si después de múltiples intentos y/o razonamientos no se llega a solución, un click sobre el botón <Ayuda> nos llevará a buen puerto. ¡Que continúe la suerte y la diversión!



         
           
  Salvador Calvo-Fernández Pérez
 
Ministerio de Educación, Cultura y Deporte. Año 2002
 
 

Licencia de Creative Commons
Los contenidos de esta unidad didáctica están bajo una licencia de Creative Commons si no se indica lo contrario.