Los puentes de Königsberg

¿Puedes realizar estos dibujos sin levantar el lápiz del papel y sin repetir ninguna línea?. Si alguna vez alguien te ha planteado esta pregunta, tu respuesta seguramente ha sido empezar a hacer líneas y líneas hasta que has llegado a alguna conclusión sobre si se puede o no.

Sin embargo, la solución a este tipo de problemas no requiere un trabajo laborioso de dibujos y dibujos, sino el pararte un momento a contar un número que caracteriza a estas representaciones. Esto se debe a que un fantástico matemático consiguió generalizar estos problemas a partir de un curiosa situación llamada "el problema de los puentes de Königsberg".

El Río Pregel y los siete puentes que lo cruzaban en verde

Königsberg era una pequeña ciudad de la Prusia oriental a orillas del báltico, a 50 kilómetros de Polonia, hoy convertida en la ciudad rusa de Kaliningrado. Los siete puentes, que fueron destruidos durante la Segunda Guerra Mundial, conectaban la ciudad con las dos grandes Islas del rio Pregel y dieron lugar en principio a la distracción habitual de los domingos entre sus habitantes y posteriormente a un problema que ocuparía el interés de los matemáticos, y que se convertiría en uno de los problemas clásicos de la geometría: ¿es posible cruzar todos los puentes sin repetir ninguno? .
La solución al problema (en este caso la imposibilidad de solución), la dio el genial matemático suizo Euler en 1736, en un artículo en el que resolvía el problema en el caso general. Este trabajo se considera como el nacimiento de la Teoría de Graficos, utilizada hoy en día en una multiplicidad de aplicaciones (Economía, Informática, ...) y también como el nacimiento de "una nueva geometría" en la que sólo importan las propiedades estructurales de un objeto y no sus medidas, y que pasaría a llamarse "Topología". (Interesante lo que dio de si el problemita).

Grafo de la situación del problema de los puentes de Konisgberg

Para obtener la solución al problema, Euler cambió los puentes por líneas (arcos), y las áreas terrestres por puntos (vértices). Este gráfico de la situación es lo que se llama grafo. Llamando «grado» de cada vértice al número de aristas que convergen en él, para que el problema tenga solución es necesario que en el grafo haya como mucho dos vértices de valencia impar (del que se sale y al que se llega). Y en el caso del grafo de Königsberg los cuatro vértices tienen grado impar, así que el problema no tiene solución.

Nota: En los problemas del principio, si calculamos el grado de los vértices llegamos a que el primero tiene solución pero el segundo no.