Problema de los Puentes de Königsberg

El problema de los 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.

Este problema fue formulado de la siguiente forma:

"Dado el mapa de Königsberg, con el río Pregel 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 solo una vez cada uno, y regresando al mismo punto de partida?"

 

Para resolver este problema Euler recurrió a una abstracción del mapa y se enfocó exclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente quedó representado mediante una línea que unía a dos puntos, y cada uno de estos puntos 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, recorra todas las líneas una sola vez y regrese al mismo punto de partida. 

 

Antes de conocer la solución de este problema, durante la Semana de las Ciencias celebrada entre el 8 y el 12 de noviembre. los alumnos y alumnas de 4º ESO C intentaron descubrir algunos grafos 'recorribles' entre unos cuantos dados, deduciendo al final qué condición deben cumplir estos grafos: no pueden tener más de dos vértices conectados a un número impar de aristas. De esta manera, concluimos que el recorrido planteado en el problema de los Puentes de Königsberg no puede realizarse, pues todos los vértices están conectados a un número impar de aristas.