Problema de los puentes de Königsberg
| ||||||
Problema de los puentes de Königsberg. También conocido como problema de los siete puentes de Königsberg, es un problema matemático resuelto por Leonhard Euler en 1736 y cuya resolución dio origen a la teoría de grafos. Su nombre se debe a Königsberg, la ciudad de Prusia Oriental y luego de Alemania que desde 1945 se convirtió en la ciudad rusa de Kaliningrado.
Descripción
Esta ciudad está atravesada por el río Pregolia. Este se bifurca y rodea con sus brazos a la isla Kneiphof, de forma que el terreno queda dividido en cuatro regiones distintas, que entonces estaban unidas mediante siete puentes llamados puente del herrero, Puente Conector, Puente Verde, Puente del Mercado, Puente de Madera, Puente Alto y Puente de la Miel. El problema se formuló en el siglo XVIII y consistía en encontrar un recorrido para cruzar a pie toda la ciudad pasando solo una vez por cada uno de los puentes y regresando al mismo punto de inicio.
Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible necesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados con un número impar de líneas. Sin embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no podría existir ningún punto conectado con un número impar de líneas.
Véase también
Fuentes
- Hector Hevia, El Problema de los Siete Puentes de Konigsberg: Leonhard Euler y la Teoria de Grafos. [1]
- Romel Félix Capcha Ventura, La Teoría de Grafos en la Resolución de Problemas Aritméticos para estudiantes del Laboratorio de Investigación e Innovación Pedagógica de la Universidad Nacional Daniel Alcídes Carrión de Pasco. [2].
