|
||
| 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: |
| ¿De qué va esto? | ||
|
|
||
| Varios | ||
Envíanos un reto para que lo publiquemos: Normas del blog ¡¡CHATEA CON LOS PASARATEROS!!  |
||
| Buscador | ||
|
||
| Suscríbete! | ||
|
||
| Feedburner Powered |
| La gente dice: | ||
|
|
||
| Ranking! | ||
|
|
||
| Enhorabuena a los premiad@s! |
| Anteriores y Archivados | ||
|
Anteriores:
Archivados:
|
||
| Categorías | ||
|
|
||
| Miembr@s del Blog | ||
| Créditos y estadísticas | ||
  Estadísticas |
||
| A todos nos gusta mirarnos el ombligo |
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?