Los puentes de Königsberg

El siguiente es un problema que me presentaron como ejemplo durante el cursado de mi carrera universitaria, y que hasta el d{ia de hoy, llevo conmigo:

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?

SOLUCIÓN
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.

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 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.

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

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.

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.