Pasa Ratos
A pasar el río2.11.06

Npi (esto quiere decir que a probar). A ver quién pasa el río por los puentes sin repetir, lo hizo Euler (según cuentan) así que... ¡a probaaaaaaaaaaaaaaaaaaaaaaaar!

AntonioT

Acertijo Propuesto por:
Etiquetas:
Comentarios:

La_puta_vaga_de_mierda dijo:
Yo que pensaba que había dejado a Euler atrás hace años y que no más álgebra, no más cálculo, no más mates discretas... no más lápiz y papel!!!! Es que nadie tiene pensado pegarse un tiro nunca más???
a las 11:39 p. m.  
Fernando* dijo:
jojojo el gran problema clásico de teoría de grafos!! que recuerdos mas ingratos!!
a las 10:25 a. m.  
AntonioT dijo:
¡Uyyyyyyyyyyyyyy! Ya sé que no queda muy bonito estropear un pasatiempo antes de que todo el mundo lo intente resolver, pero es que esto es un tema interesantísimo, es nada más y nada menos que topología. Además el problema de los puentes de Königsberg tien mucha más historia de lo que pueda parecer. Así que me vais a permitir un comentario un poco extenso.

Este plano es de 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. 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.

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.

El problema es el mismo que los de pintar un sobrecito sin levantar el lápiz, que probablemente todos hemos resuelto de niños. 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.

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. 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.

Pues bien, 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 contamos los lados de cada vértice del sobrecito vemos que sólo los dos inferiores tienen un número impar. Para dibujarlo tendremos que comenzar por uno de ellos y terminar por el otro, de esta manera es sumamente fácil.

Volviendo a los puentes, si consideramos los puentes como caminos y los puntos en tierra como vértices, obtenemos la siguiente figura:

Pinchar aquí

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 podríamos encontrar imposible resolver?

Esto lo resolvió un señor llamado Leonard Euler en 1736 y dio lugar al nacimiento de la teoría de grafos.

¿A que tenía tela el tal Euler?
a las 10:59 a. m.  
La_puta_vaga_de_mierda dijo:
Venga, ahora un ejercicio de redes y vuelvo a econtrarme en segundo de carrera :D
a las 12:59 p. m.  
laceci dijo:
Yo si supe algo de esto, lo olvidé completamente... Si lo resuelvo, será por redes neuronales y lógica difusa.
a las 1:02 p. m.  
Fernando* dijo:
Bravo, AntonioT. Estupenda explicación. hasta amena ha sido :D:D
a las 2:47 p. m.  
Maximínimo dijo:
¡Qué chico más listo! Así da gusto, no como yo, que para editar el p... código del nombrecito del ganador se me va todo a tomar por c...
a las 6:52 p. m.  
¿De qué va esto?
Acertijos, pasatiempos y juegos para pensar.
Varios
Envíanos un reto para que lo publiquemos:



Normas del blog

¡¡CHATEA CON LOS PASARATEROS!!

Buscador
powered by: Google
Suscríbete!
Pasa Ratos
Feedburner Powered
La gente dice:
Ranking!
Enhorabuena a los premiad@s!
Anteriores y Archivados
Anteriores:

(En rojo y negrita, los NO Resueltos)


Archivados:
Categorías
Miembr@s del Blog
Créditos y estadísticas
Con FireFox disfrutarás más!

Powered by Blogger

Estadísticas
A todos nos gusta mirarnos el ombligo