Retos 296

Pasa una sola vez

Claudia Hernández

Shutterstock

Kaliningrado es una ciudad rusa que alguna vez se llamó Königsberg y que pertenecía a Prusia, un territorio que se reconfiguró después de la Segunda Guerra Mundial. Esta ciudad es famosa por ser el lugar de nacimiento del filósofo Immanuel Kant y de una rama de las matemáticas llamada teoría de grafos. El río Pregolia dividía la ciudad en cuatro regiones que se conectaban por medio de siete puentes. En el siglo xviii se planteó el problema conocido como el de los puentes de Königsberg: ¿es posible recorrer las regiones pasando por todos los puentes una sola vez y terminando en el punto donde se comenzó? Por más empeño que se puso nadie logró resolverlo. En 1736 el matemático suizo Leonhard Euler explicó que se trataba de una tarea imposible.

Recorridos equivalentes

Lo primero que hizo Euler fue simplificar el problema (porque eso hacemos quienes nos dedicamos a las matemáticas) y no hacer los recorridos a pie, sino representándolos en una imagen donde se distingue la tierra del agua y pueden verse las regiones de tierra que conectan los puentes: La ciudad entonces pasó a ser un grafo y la tarea se transformó de “pasar por cada puente” a “recorrer todas las aristas”. Hoy en día planteamos el reto como “recorrer la figura sin levantar nunca el lápiz del papel”. El primer reto es explicar por qué podemos decir que “recorrer la ciudad a pie” resulta equivalente a “recorrer la figura sin levantar el lápiz”.

Entre grafos y aristas

Como demostró Euler, la tarea es imposible porque el grafo anterior no se puede recorrer pasando por todas las aristas una sola vez y sin levantar el lápiz. El segundo reto consiste en recorrer estos otros grafos con esas condiciones.

Sin salida

El tercer reto consiste en encontrar una diferencia sustancial entre los tres grafos y descubrir qué hace que sólo uno de ellos cumpla las condiciones iniciales de pasar por todas las aristas sin levantar el lápiz y terminar en el punto donde se comenzó. Pista: no se trata de la cantidad de aristas, sino de lo que ocurre en cada vértice.