Actividad: Los siete puentes de Königsberg
La parte antigua de la ciudad de Königsberg tiene siete puentes:
¿Puedes
dar un paseo por la ciudad, visitar cada parte de la ciudad
y cruzar
cada puente una sola vez?
Esta pregunta le fue dada hace muchos años a un famoso matemático llamado Leonhard Euler ... ¡pero intentemos responderla nosotros mismos!
Y en el camino aprenderemos un poco sobre "Teoría de grafos".
Simplificando
Podemos simplificar el mapa de arriba a esto:
Hay cuatro territorios ciudad: el territorio al norte del río, el territorio al sur del río, la isla y la península (el pedazo de tierra a la derecha)
Vamos a etiquetarlos como A, B, C y D:
Para "Visitar cada parte de la ciudad" debes visitar los puntos A, B, C y D. Y debes cruzar cada puente p, q, r, s, t, u y v solo una vez. |
Y podemos simplificarlo aún más a esto:
Entonces,
en lugar de dar paseos largos por la
ciudad,
ahora puedes simplemente dibujar líneas con un lápiz.
Tu turno
¿Puedes dibujar cada línea p, q, r, s, t, u y v solo una vez, sin sacar el lápiz del papel (puedes comenzar en cualquier punto)?
Pruébalo a ver si puedes.
...
¿Tuviste éxito?
Bueno ... demos un paso atrás y probemos algunas formas más simples.
Prueba estos (recuerda: dibuja todas las líneas, pero nunca pases por encima de una línea más de una vez y no retires el lápiz del papel).
Pon tus resultados aquí:
Forma | ¿Éxito? |
1 | Sí |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 |
Entonces, ¿cómo podemos saber cuáles funcionan y cuáles no?
¡Investiguemos!
Pero primero, es hora de aprender algunas palabras especiales:
|
Sí, se llama "Gráfica" ... pero NO es este tipo de gráfica: Ambas
se denominan "gráficas". |
|
|
Ejemplos:
El diagrama 7 tiene
|
El diagrama 8 tiene
|
Camino de Euler
Bien, imagina que las líneas son puentes. Si los cruzas una vez solo habrás resuelto el rompecabezas, entonces ...
... lo que queremos es un "Camino Euler" ...
... y aquí hay una pista para ayudarte: podemos decir qué grafos tienen un "Camino de Euler" contando cuántos vértices tienen un grado impar.
Entonces, completa esta tabla:
Forma | ¿Camino de Euler? | Vértices | Cuántos con grado par | Cuántos con grado impar |
1 | Sí | 4 | 4 | 0 |
2 | ||||
3 | ||||
4 | ||||
5 | ||||
6 | ||||
7 | ||||
8 |
¿Existe un patrón?
No leas más hasta que hayas encontrado algún tipo de patrón ... la respuesta está en la tabla.
OK ... la respuesta es ...
El número de vértices de grado impar debe ser cero o dos.
Si no es así, no existe un "Camino Euler"
Y si hay dos vértices con grados impares, entonces son los vértices inicial y final.
Y la razón no es difícil de entender.
Un camino conduce a un vértice por un borde y sale por un segundo borde.
Entonces, los bordes deben venir en pares (un número par).
Solo el punto inicial y final pueden tener un grado impar.
Ahora volvamos a la pregunta del puente Königsberg:
Los
vértices A, B y D tienen grado 3 y el vértice C
tiene grado 5, por lo que esta gráfica tiene cuatro vértices de
grado impar. Entonces
no
tiene un Camino Euler.
¡Hemos
resuelto la cuestión del puente de Königsberg como lo hizo Euler
hace casi 300 años!
Ejercicio adicional: ¿Cuál de las siguientes gráficas tiene un camino de Euler?
Forma | ¿Camino de Euler? | Vértices | Cuántos con grado par | Cuántos con grado impar |
9 | ||||
10 | ||||
11 | ||||
12 | ||||
13 | ||||
14 |
Notas al pie
Leonhard Euler (1707-1783), matemático suizo, fue uno de los matemáticos más grandes y prolíficos de todos los tiempos. Euler pasó gran parte de su vida laboral en la Academia de Berlín en Alemania, y fue durante ese tiempo que se le dio la pregunta de "Los siete puentes de Königsberg" para resolver que se ha hecho famosa.
La ciudad de Königsberg se extiende a ambos lados del río Pregel. Anteriormente estaba en Prusia, pero ahora se conoce como Kaliningrado y está en Rusia. Königsberg estaba situado cerca de la desembocadura del río y tenía siete puentes que unían los dos lados del río y también una isla y una península.
Respuesta a la tabla de diagramas:
Forma | ¿Camino de Euler? | Pares | Impares |
1 | Sí | 4 | 0 |
2 | Sí | 2 | 2 |
3 | NO | 0 | 4 |
4 | NO | 1 | 4 |
5 | Sí | 2 | 2 |
6 | Sí | 3 | 2 |
7 | Sí | 3 | 2 |
8 | Sí | 4 | 2 |