LOS SIETE PUENTES DE KÖNOGSBERG

Los Siete Puentes de Königsberg:

"El inicio de la Teoría de Grafos".

.

El llamado problema de "los siete puentes de Königsberg" fue lo que dio origen a la teoría de grafos.
Cabe señalar que Königsberg era Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia Rusa.

Durante mucho tiempo se intentó resolver el siguiente problema:


En la ciudad de Königsberg hay una isla y el río Pregel que la rodea se divide en dos brazos (como aparece en la imagen). La distintas zonas de tierra están unidos mediante siete puentes (color rojo). ¿Es posible dar un paseo por la ciudad, empezando por cualquiera de las cuatro partes de tierra firme, cruzando cada puente una y sólo una vez y volver nuevamente al punto de partida?

Después de un tiempo, en 1736, Leonhard Euler dio respuesta a este problema, dando origen a la teoría de grafos. Él representó por un punto cada sector de tierra y por una línea cada puente, uniendo los distintos puntos con tantas líneas como puentes haya entre dichos sectores, creando de esta forma, al primer grafo de la historia.


La representación de Euler fue similar a la siguiente imagen:

Euler se dio cuenta que la cantidad de líneas de cada punto tendría que ser par, para así poder entrar y salir de dicho punto, ocupando tan solo una vez cada puente.

En el problema de Königsberg, Euler demostró que era imposible recorrer la ciudad de la forma pedida, ya que el número de líneas que llegan a cada punto es impar y ésto implica que no es posible recorrerlos pasando una sola vez por cada uno de los puentes, es decir, no había solución paea ese problema.