Desfiles – 2 – 7 Puentes de Königsberg
Este es un mapa de Königsberg que muestra el río que la atraviesa, la isla en medio del río y los siete puentes que lo cruzan. Los habitantes de Königsberg querían un desfile que pasara por cada uno de sus puentes exactamente una vez. Sin embargo, no lograban encontrar una ruta que recorriera los siete puentes.
EL RETO
Si es posible, busquen una ruta para el desfile que cruce cada uno de sus puentes exactamente una vez. Si no pueden, expliquen por qué es imposible.
EXPLORACIÓN
Si se añade otro puente sobre el río, ¿eso facilitaría o complicaría el problema?
Notas
EL RETO
Comencemos por traducir este problema a uno que tenga aristas que debamos recorrer. Como vimos en el rompecabezas de la semana "Desfiles", es crucial que no haya más de dos nodos donde aparezca un número impar de lados.
Debido a que los cuatro nodos tienen un número impar de aristas entrantes, ¡será imposible encontrar una ruta para el desfile!
EXPLORACIÓN
Si añades un puente más sobre el río en cualquier lugar, te resultará muy fácil resolverlo.
este problema. Eso se debe a que dos de los cuatro nodos tendrán entonces un número par de aristas que les llegan,
y eso dejará solo dos nodos con un número impar de aristas que llegan a ellos.