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

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:

Un punto se llama vértice Una línea se llama borde. El diagrama completo se llama grafo*. *En algunos países también  le llaman gráfica

Sí, se llama "Gráfica" ... pero NO es este tipo de gráfica: Ambas se denominan "gráficas". Pero son cosas diferentes. Así son las cosas.

 

El número de aristas que conducen a un vértice se llama grado.

Una ruta alrededor de un gráfico que visita cada vértice una vez se llama ruta simple. Una ruta alrededor de un gráfico que visita cada borde una vez se llama ruta de Euler.

Ejemplos:

El diagrama 7 tiene 5 vértices: A, B, C, D y E 8 bordes: AB, BC, CD, DA, AE, BE, AC y BD Los vértices A y B tienen grado 4 Los vértices C y D tienen grado 3 El vértice E tiene grado 2		El diagrama 8 tiene 6 vértices: A, B, C, D, E y F 10 bordes: AB, BC, CD, DA, AF, BF, CF, DF, AE y BE Los vértices A, B y F tienen grado 4 Los vértices C y D tienen grado 3 El vértice E tiene grado 2

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.

 

 

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