El problema de los siete puentes de Königsberg (Prusia oriental en el siglo XVIII -ciudad natal de Kant- y actualmente, Kaliningrado, provincia rusa) es un célebre problema matemático que fue resuelto por Leonhard Euler en 1736 y dio origen a la Teoría de los grafos.
Consiste en lo siguiente:
Dos islas en el río Pregel que cruza Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?
Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo terminando en el punto de partida sin repetir las líneas?
Euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto, y para regresar al punto de partida, por caminos distintos en todo momento). En teoría de los grafos esta idea se corresponde con la posibilidad de encontrar un Ciclo Euleriano en un grafo.
El problema del sobre
En primer lugar, hay que decir un detalle sobre la forma. No importa que cada lado sea perfectamente recto, sino que puede hacer eses o un extraño camino que incluso puede cambiar totalmente la forma del sobrecito. Lo que sí importa es que tenga los mismos vértices y que los caminos vayan de uno a otro de la misma manera. Si es así, a grandes rasgos, se dice entonces que estas figuras son topológicamente iguales:
Asumido esto, empezaremos por decir que un vértice es aquel punto donde se unen dos o más caminos. Hay dos tipos de vértice. Al primero de ellos lo llamaremos vértice de paso. En él llega un camino y sale otro, llega un tercero y sale un cuarto. ¿Adivináis?, un vértice de paso tiene, por tanto, un número par de caminos (o lados). Un vértice que no sea de paso tendrá un número impar de caminos, y será donde empiece o acabe el grafo. Os los muestro en la siguiente imagen:
Pues bien, afirmamos que para que un grafo pueda ser dibujado sin levantar el lápiz del papel tiene que tener, como máximo dos vértices que no sean de paso, o sea, dos vértices con un número impar de lados. Para realizar el trazo correctamente tendremos que empezar por uno de ellos y acabar en el otro. Si esto lo aplicamos al problema del sobrecito, lo único que hemos de hacer es contar cuántos lados hay en cada vértice:
Ya vemos que, efectivamente, los vértices inferiores son los dos impares y el resto par. De manera que para hacerlo hemos de empezar por uno de ellos y finalizar en el otro (os recomiendo que lo hagáis y sorprenderos qué bien funciona esto, veréis que sólo si empezáis en los vértices de 3 lados podréis hacerlo de un solo trazo y de varias formas diferentes).
Y ahora vamos ahora al problema de los puentes. Consideramos los puntos de tierra como vértices y los puentes como camino. Si lo dibujamos como un grafo tendremos lo siguiente.
Ahora hemos de contar los lados de cada vértice. Hay 4 vértices y todos ellos impares. Por tanto, no podremos hacer un paseo pasando una y sólo una vez por cada puente. Lo impresionante de todo esto es que podréis aplicarlo a cualquier problema similar. ¿No os parece mucho más fácil contar caminos que probar todas las posibilidades? ¿No os parece increíble que con cuatro sencillas reglas hayamos dado carpetazo a un asunto que a priori encontrábamos imposible reslover?
Fuentes:
http://es.wikipedia.org/wiki/Problema_de_los_puentes_de_K%C3%B6nigsberg