Gráficos y RedesLos puentes de Königsberg
Uno de los primeros matemáticos en pensar en gráficos y redes fue
El río Pregel divide Königsberg en cuatro partes separadas, que están conectadas por siete puentes. ¿Es posible caminar por la ciudad cruzando todos los puentes exactamente una vez, pero no más de una vez? (Puede comenzar y terminar en cualquier lugar, no necesariamente en el mismo lugar).
Intenta encontrar una ruta válida dibujando en estos mapas:
Map 1
Map 2
Map 3
Map 4
En el caso de Königsberg parece imposible encontrar una ruta válida, pero algunas de las otras ciudades sí funcionan. Euler logró encontrar una regla simple que se puede aplicar a cualquier ciudad, sin tener que probar muchas posibilidades, utilizando la teoría de grafos.
Primero, necesitamos convertir los mapas de la ciudad en gráficos con bordes y vértices. Cada isla o región de tierra está representada por
Ahora el problema de "recorrer una ciudad mientras se cruza cada puente exactamente una vez" se ha convertido en un problema de "dibujar un gráfico con un trazo continuo y trazar cada borde exactamente una vez".
En el papel, crea algunos gráficos diferentes y luego trata de determinar cuáles se pueden dibujar con un solo trazo continuo.
Al igual que en los mapas de la ciudad antes, encontramos que algunos gráficos son posibles mientras que otros no. Para ayudarnos a entender por qué, etiquetemos cada vértice con su
Al comparar estos números para los gráficos que son posibles y los que no son posibles, parece que se puede dibujar un gráfico si no
Si regresa al mapa de Königsberg, encontrará que hay más de dos islas con un número impar de puentes. Por lo tanto, una ruta que cruza cada puente exactamente una vez es realmente imposible, y esto es lo que descubrió Leonard Euler.
El descubrimiento de Euler puede no parecer particularmente útil en la vida real, pero los gráficos son la base de muchos otros problemas geográficos, como encontrar direcciones entre dos ubicaciones. Descubriremos más de estas aplicaciones más adelante.