Problema de los puentes de Knigsberg

El problema de los puentes de Knigsberg es un clebre problema matemtico, resuelto por Leonhard Euler en

1736 y cuya resolucin dio origen a la teora de grafos.

Su nombre se debe a Knigsberg, el antiguo nombre que reciba la ciudad rusa de Kaliningrado, que durante el

siglo XVIII formaba parte de Prusia Oriental, como uno de los ducados del Reino de Prusia.

El problema fue formulado en el siglo XVIII y consista en encontrar un recorrido para cruzar a pie toda la

ciudad, pasando slo una vez por cada uno de los puentes, y regresando al mismo punto de inicio.

Solucin de Euler

Euler determin, en el contexto del problema, que los

puntos intermedios de un recorrido posible necesariamente

han de estar conectados a un nmero par de lneas. En

efecto, si llegamos a un punto desde alguna lnea, entonces

el nico modo de salir de ese punto es por una lnea

diferente. Esto significa que tanto el punto inicial como el

final seran los nicos que podran estar conectados con un

nmero impar de lneas.

Sin embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no

podra existir ningn punto conectado con un nmero impar de lneas.

En particular, como en este diagrama los cuatro puntos poseen un nmero impar de lneas incidentes (tres de

ellos inciden en tres lneas, y el restante incide en cinco), entonces se concluye que es imposible definir un

camino con las caractersticas buscadas que son los 7 puentes de Knigsberg.