Euler y la teoría de grafos

La teoría de grafos se inició gracias a un problema turístico-recreativo que resolvió Leonhard Euler. Dice la historia que en 1736 el eminente matemático se detuvo, en uno de sus viajes, en Königsberg (actual Kaliningrado). Dicha ciudad estaba dividida en cuatro partes, conectadas por siete puentes, al pasar por ella un río.

Una versión simplificada de esta disposición, numerando los puentes y designando con letras cada una de las cuatro áreas urbanas, sería la siguiente:

Respecto al problema de los puentes, Euler escribió: «El problema que, según entiendo, es muy bien conocido, se enuncia así: en la ciudad de Königsberg, en Prusia, hay una isla llamada Kneiphof, rodeada por los dos brazos del río Pregel. Hay siete puentes que cruzan los dos brazos del río. La cuestión consiste en determinar si una persona puede realizar un paseo de tal modo que cruce cada uno de los puentes una sola vez. Se me ha informado de que mientras unos negaban la posibilidad de hacerlo y otros lo dudaban, nadie sostenía que fuese posible realmente.»

La respuesta del propio Euler fue que no era posible y basó su negativa en el siguiente tipo de razonamiento: prescindiendo de la geografía peculiar de la ciudad y su entorno puede trazarse un esquema de la misma mediante cuatro puntos A,B,C,D  (que se correspondan con las cuatro partes de la ciudad), y unir con curvas arbitrarias aquellos puntos conectados en la realidad por puentes:

El problema inicial es, de hecho, equivalente al problema (basado en la figura anterior) según el cual si partiendo de uno de los cuatro puntos puede trazarse un itinerario que englobe todas las curvas una sola vez. Si ello fuese posible el número de líneas por cada punto debería ser par y, en cambio, todos los puntos tienen un número impar de líneas. Por tanto, el problema no tiene solución.

Los puentes de Königsberg fueron destruidos durante la Segunda Guerra Mundial, pero la anécdota, atribuida a Euler, fue el principio de una teoría matemática de gran utilidad y brillantez: la teoría de grafos.

📖#Fuente

"Mapas del metro y redes neurona"

 Claudi Alsina