Los puentes de Königsberg
¿Recordáis cuando se os pedía hacer aquel sobrecito de un solo trazo, sin levantar el bolígrafo de papel? ¿Sabías que existe una rama de las matemáticas llamada topología que lo explica perfectamente?
Pues bien, nuestra historia de hoy empieza en la ciudad de Königsberg (hoy Kaliningrado), en territorio Ruso a unos 50 kilómetros de la frontera con Polonia. En el pasado perteneció a Prusia. Uno de sus habitantes más ilustres fue el filósofo Immanuel Kant. ¿Por qué os hablo de esta ciudad? Pues porque esta ciudad es atravesada por dos ríos que confluyen en ella dejando en medio una isla y tiene 7 puentes que conectan regiones de terreno separadas por el agua.
Os muestro el plano y los puentes:
En el siglo XVIII se hizo popular la adivinanza o pasatiempo de averiguar si era posible cruzar los siete puentes de la ciudad pasando una y sólo una vez por cada uno de ellos. Este problema puede resolverse, por supuesto, probando todos los posibles itinerarios. Pero si tenemos cabeza es para evitar hacer las cosas a base de fuerza bruta.
De momento, volvamos al tema del sobrecito. 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?
¿Quién resolvió esto y cuándo? ¿Un potente grupo de desconocidos matemáticos del siglo XX?. Pues no, un solo hombre llamado Leonard Euler en 1736 y dio nacimiento a la teoría de grafos. Por supuesto, un personaje con esta agilidad mental hizo muchas más cosas, pero las dejaremos para otras historias.
Fuentes:
http://es.wikipedia.org/wiki/Problema_de_los_puentes_de_K%C3%B6nigsberg
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_los_grafos
http://www.astrocosmo.cl/anexos/p-p_konigsberg.htm
El día 1 de Agosto de 2005 a las 18:03
Trobo molt interessant el tema dels ponts de Könnigsberg; de fet jo també l’he estudiat; però hi ha algu que no em quadra, perquè t’expresses en català? “lamevaweb” deixa força clar que és exclusiu per a diaris personals en català oi?, et convido a que t’ho repensis i a partir d’ara escriguis en català.
El día 1 de Agosto de 2005 a las 18:03
perdo, volia dir perquè t’expresses en castellà?
El día 1 de Agosto de 2005 a las 18:21
Tus artículos son siempre muy buenos, pero para mi gusto este lo has bordado. Enhorabuena y gracias por el buen nivel.
El día 1 de Agosto de 2005 a las 18:34
Remo: muchísimas gracias.
El día 1 de Agosto de 2005 a las 18:37
Joaquim:
tinc amics de fora de Catalunya que em segueixen. Daltrabanda, vaig demanar per e-mail a lamevaweb permís espressament per fer-ho i em van dir (paraules textuals):
“faltaria més, totes les aportacions son benvingudes”.
Cosa que els hi agraeïxo.
Si algú vol traduïr els articles en algun lloc, no tindré problema en posar el link.
Salut!!
El día 2 de Agosto de 2005 a las 16:36
La resolución del problema de Königsberg de Euler es de una sencillez y elegancia aplastantes.
Sí, un día tenías que relatar los innumerables logros de Euler, uno de los mejores matemáticos de la historia (¿el más grande?).
Saludos
El día 2 de Agosto de 2005 a las 16:45
Pues no vas desencaminado. Aunque no me guste decirlo de esa manera, es verdad, fue el más grande; al menos fue el que más publicaciones científicas ha hecho en la historia.
Pero tranquilo, tranquilo, que algún articulito más caerá, sin duda (tengo un libro de más de 200 páginas que habla de muchos de sus logros).
Es demasiado bueno para no dedicarle más de uno.
Saludos
El día 3 de Agosto de 2005 a las 00:13
Muchas gracias por escribir en castellano tu blog, asi muchas mas personas pueden leerlo.
El día 21 de Septiembre de 2005 a las 22:33
La historia de los puentes de Königsberg no termina con la solución de Euler. Dice la leyenda que el jerifalte de la ciudad (o simplemente alguien con autoridad), al enterarse de que no era posible caminar por los siete puentes pasando por ellos una unica vez, pero que sí era posible con ocho, ordenó construir un octavo puente.
El día 22 de Septiembre de 2005 a las 11:12
Pues sí señor, con un octavo puente sería posible.
Me gustaría que alguien corroborase o me dijese dónde puedo verificarlo.
Saludos y gracias por el comentario