Cambiar idioma

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Iniciar sesión en Mathigon

o

Nueva cuenta     Restablecer la contraseña     

Gráficos y Redes
Introducción
Los puentes de Königsberg
Apretones de manos y citas
Gráficos Planos
Mapa para colorear
El problema del vendedor ambulante
Problemas de programación
Gráficos en la vida cotidiana

Compartir

Restablecer progreso

Esto eliminará su progreso y los datos de chat de todos los capítulos de este curso y no se puede deshacer.

Glosario

Seleccione una de las palabras clave de la izquierda ...

Gráficos y RedesLos puentes de Königsberg

Tiempo de leer: ~20 min

Uno de los primeros matemáticos en pensar en gráficos y redes fue Leonhard Euler . Euler estaba intrigado por un viejo problema relacionado con la ciudad de Königsberg, cerca del mar Báltico.

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 y cada puente que conecta dos regiones está representado por un correspondiente

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 grado . Luego podemos colorear los vértices de diferentes maneras e intentar revelar un patrón:

Value
Size
Prime Numbers
Even and Odd

These graphs are possible:

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

These graphs are not possible:

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

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 . Esta condición puede explicarse si observamos solo un vértice único en el gráfico:

Here you can see a single, magnified vertex in a graph.
If we draw the graph, we will eventually have an edge leading towards this vertex, and then another one leading away. This makes two edges meeting at the vertex.
Maybe the vertex is a crossing rather than a corner. In that case there will be another edge leading towards the vertex, and another edge leading away. Now we have four edges.
And in some graphs, there may even be a third pair of edges leading towards and away from the vertex. Now there are six edges.
Notice that, either way, there always is an even number of edges meeting at the vertex.
The only two exceptions are the vertices where the path starts, and where it ends – these two may have an odd number of edges. If the start and end point are the same, all vertices in the graph are even.

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.

Archie