El problema del puente de los siete Königsberg

El problema de los puentes de Königsberg [ 1 ] [ 2 ] [ 3 ] _____  [9] [10] ) es un viejo problema matemático que preguntaba cómo era posible cruzar los siete puentes en el centro de el viejo Königsberg sin pasar dos veces por ninguno de ellos. Fue resuelto por primera vez en un artículo fechado en 1736 [2] [11] por el matemático Leonhard Euler , quien demostró que esto era imposible e inventó los ciclos de Euler en el curso de la prueba . La solución de Euler del problema del puente de Königsberg fue la primera aplicación de la teoría de grafos , pero sin usar el término " gráfico " y sin dibujar diagramas de gráficos.   

Historia

En el centro de Königsberg (ahora Kaliningrado ) en el río Pregel (ahora Pregolya ) hay dos islas: Kneiphof (ahora isla Immanuel Kant) y Lomse (ahora isla Oktyabrsky ). A orillas del Pregel, al norte de la isla de Kneiphof se encuentra Altstadt , al sur, Vorstadt . Se construyeron puentes a través del Pregel conectando estos cuatro distritos [12] . La figura de la derecha muestra el centro de Königsberg en un mapa de 1652 con las designaciones: A - Altstadt, B - Kneiphof, C - Lomse y D - Vorstadt.

La historia de la construcción de puentes en Königsberg

Los siete primeros puentes del centro de Königsberg, que conectan Altstadt, Kneiphof, Lomse y Vorstadt, se construyeron en los años siguientes en el siguiente orden [12] . Los números de puentes en el orden en que fueron construidos se muestran en la figura de la derecha.

1. Tienda puente (1286)

El primer puente de Königsberg data de 1286. Conectado Altstadt y Kneiphof. Pertenecía a la ciudad de Altstadt y proporcionaba a la ciudad un fácil acceso a los mercados de Kneiphof [12] .

2. Puente Verde (1322)

El segundo puente de Königsberg fue construido en 1322. Conectó Kneiphof con Vorstadt y proporcionó un fácil acceso a áreas remotas. El puente se llamó Verde debido a las ondas verdes que sirven como fondo del escudo de armas de Kneiphof [12] .

3. Puente de trabajo (1377)

En el siglo XIV había un matadero al este de Vorstadt. Para facilitar el transporte de carne, se construyó un tercer puente entre Kneiphof y Vorstadt en 1377 [12] .

4. Puente del herrero (1397)

en 1397, se construyó el cuarto Puente del Herrero en la parte noreste de Kneiphof, que comenzó cerca de los talleres de herrería en Altstadt [12] .

Si se dibuja un gráfico sobre estos cuatro puentes , entonces será Euler , es decir, los cuatro puentes se pueden pasar por alto una vez a lo largo de una ruta cerrada, comenzando desde cualquier lugar. Los residentes podían dar esos paseos [12] .

5. Puente de madera (1404)

La madera se recolectaba en la isla de Lomse, y un quinto puente entre Altstadt y Lomse, construido entre 1400 y 1404, facilitaba la entrega de madera [12] .

6. Puente alto (1506)

El sexto puente fue construido en 1506 para conectar Lomse y Vorstadt [12] .

7. Puente de miel (1542)

El séptimo de los puentes de Euler, que conecta las dos islas, se completó en 1542. Fue construido por los habitantes de Kneiphof para pasar a la orilla norte, evitando los dos puentes de Kneiphof controlados por Altstadt. Según la leyenda, Kneiphof entregó un barril de miel a Altstadt para obtener permiso para construir un puente [12] .

Entonces, en 1542, los siete puentes de Königsberg, considerados por Euler, estaban en su lugar. Ahora los habitantes no podían pasar por alto todos los puentes a la vez [12] .

Historial de problemas

El surgimiento de la rama de la teoría matemática de grafos se asocia con acertijos matemáticos, y durante mucho tiempo la teoría de grafos fue "frívola" y completamente asociada con juegos y entretenimiento. Este destino de la teoría de grafos repite el destino de la teoría de la probabilidad , que también encontró por primera vez su aplicación solo en los juegos de azar [13] .

Los habitantes de Koenigsberg practicaban una especie de juego: cómo pasar por todos los puentes de la ciudad para que la ruta no cruzara ninguno de ellos dos veces [3] . “Según escuché”, escribió Leonhard Euler, “algunos niegan que esto se pueda hacer, otros lo dudan, pero nadie confirma tal posibilidad. [14] »

Historial de publicaciones del artículo de Leonhard Euler

Leonhard Euler, destacado matemático y mecánico suizo, prusiano y ruso , académico de la Academia de Ciencias de San Petersburgo, se interesó por este juego. La historia de la publicación del famoso artículo de Leonhard Euler "La solución de un problema relacionado con la geometría de la posición", escrito en relación con esto, tiene las siguientes etapas conocidas de publicaciones modernas:

• primero , el 26 de agosto  ( 6 de septiembre )  de 1735 [15] , Euler presentó un artículo en la Conferencia de la Academia de Ciencias de San Petersburgo [2] ;
• luego, en 1736, Euler, como parte de su correspondencia científica, envió las siguientes dos cartas:

• 13  ( 24 )  de marzo de 1736 - carta a Johann Jacob Marinoni , astrónomo y matemático austriaco, fechada el 13 [24] de marzo de 1736, Petersburgo. Esta carta está enteramente dedicada al problema del puente de Königsberg [16] [17] ;
• 3  ( 14 )  de abril de 1736 - una carta a Karl Leonard Gottlieb Oehler , un político y astrónomo alemán, fechada el 3 de abril [14] de 1736, en Petersburgo. Al final de esta carta, hablamos de las ideas principales del trabajo [16] [18] ;

• en 1741 en San Petersburgo , el artículo de Euler fue finalmente publicado en latín con la fecha de 1736 [16] [19] :

Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. Pág. 128-140.

Traducido [14] :

Leonardo Euler. Solución de un problema relacionado con la geometría de posición / Actas de la Academia de Ciencias de San Petersburgo. 8 (1736). 1741, págs. 128-140.

Dado que la publicación del artículo de Leonhard Euler "La solución de un problema relacionado con la geometría de la posición" está fechada en 1736, y las dos letras mencionadas anteriormente datan de este año, este año es designado por la comunidad matemática mundial como la fecha de nacimiento del sección de teoría de grafos matemáticos [2] .

Una solución moderna al problema

Planteamiento del problema

El problema de los puentes de Königsberg está formulado de manera diferente por diferentes autores.

1. La ruta es arbitraria

En relación con estos puentes, se planteó la cuestión de si es posible caminar sobre ellos de tal manera que se pase por cada uno de estos puentes, y exactamente una vez.

— Leonard Euler. Solución de un problema relacionado con la geometría de posición [14]

Para los habitantes de Königsberg, había una especie de juego: encontrar una ruta para caminar por la ciudad que pasara por cada uno de los puentes que se muestran en la figura exactamente una vez.

— Fritsch R. y otros Capítulos seleccionados en teoría de grafos [3]

2. La ruta debe estar cerrada

La tarea era la siguiente: encontrar una ruta para pasar por las cuatro partes de la tierra, que comenzara en cualquiera de ellas, terminara en la misma parte y pasara exactamente una vez por cada puente.

—Frank Harari. Teoría de grafos [1]

3. Las rutas circulares deben comenzar en todas las partes de la ciudad.

De hecho, se requiere encontrar cuatro rutas sin pasar por los puentes de Königsberg, comenzando en cuatro partes de la ciudad.

La pregunta era, ¿es posible hacer una caminata de tal manera que, habiendo salido de la casa, se regrese, pasando exactamente una vez por cada puente?

— Ore O. Gráficos y sus aplicaciones [20]

Construyendo un gráfico de tareas

La solución moderna del problema de los puentes de Königsberg comienza con la construcción de un gráfico del problema (ver la figura de la derecha) [21] :

• los picos del gráfico son cuatro partes del centro de Königsberg, en el que la ciudad está dividida por dos brazos y un cauce fluvial;
• las nervaduras del gráfico son los siete puentes en el centro de la ciudad;
• los vértices finales de los bordes son partes del centro de Königsberg conectado por estos puentes.

El problema del puente de Königsberg se puede reformular en términos de teoría de grafos de la siguiente manera [22] :

• ¿El gráfico del problema del puente de Königsberg tiene un ciclo de Euler o al menos una cadena de Euler ?

Teoremas de Euler

Comencemos con las definiciones, pasemos a los teoremas y terminemos con los corolarios [22] :

• Cadena de Euler : una secuencia de aristas (las aristas vecinas tienen un vértice común) que pasa por alto todas las aristas del gráfico una vez;
• El ciclo de Euler es una cadena de Euler cerrada.

Los siguientes dos teoremas aparecieron por primera vez en el artículo de Leonhard Euler sobre los puentes de Königsberg [22] :

• Primer teorema de Euler, 1736. Un grafo con dos o más vértices tiene un ciclo de Euler si y sólo si cada vértice tiene un número par de aristas;
• Segundo teorema de Euler, 1736. Un gráfico con dos o más vértices tiene un único camino de Euler si y solo si exactamente dos vértices tienen un número impar de aristas.

De estos dos teoremas [22] se pueden deducir tres consecuencias :

• si un gráfico con dos vértices que contienen un número impar de aristas tiene una cadena de Euler, entonces estos dos vértices son los vértices inicial y final de la cadena;
• un gráfico con dos o más vértices tiene una cadena de Euler si y solo si cada vértice tiene un número par de aristas, o exactamente dos vértices tienen un número impar de aristas;
• el problema del puente de Königsberg no tiene solución, ya que cuatro vértices en la gráfica de este problema tienen un grado impar.

Solución del problema según Leonhard Euler

Planteamiento del problema

Leonhard Euler en su famoso artículo formuló el problema de los siete puentes de Königsberg de la siguiente manera [14] :

2. Esta tarea, me dijeron, es bastante conocida y está relacionada con esto. En la ciudad de Königsberg, en Prusia, hay una isla llamada Kneiphof ; el río que lo rodea se divide en dos brazos, que se pueden ver en la figura. Los brazos de este río están atravesados ​​por siete puentes a , b , c , d , e , fy g . En relación con estos puentes, se planteó la cuestión de si es posible caminar sobre ellos de tal manera que se pase por cada uno de estos puentes, y exactamente una vez.

— Leonard Euler. Resolviendo un problema relacionado con la geometría de posición

Solución del problema

Leonhard Euler formuló su método de la siguiente manera (ver figura arriba) [23] :

4. Todo mi método se basa en la notación adecuada para los pasajes individuales de los puentes. Uso las letras mayúsculas A, B, C, D para indicar las áreas individuales en las que el río divide la tierra. Por lo tanto, si alguien se mueve del área A al área B a través de un puente a o b, denoto el paso del puente con el símbolo AB.

— Leonard Euler. Resolviendo un problema relacionado con la geometría de posición

En lenguaje moderno, esto significa que la gráfica de los puentes de la ciudad corresponde a la gráfica, que es:

• cuatro picos según las designaciones de las cuatro partes del centro de la ciudad;
• los vértices están conectados por siete aristas-puentes según las designaciones de siete puentes.

Una solución bastante moderna y simple de Leonhard Euler del problema del puente de Königsberg es la siguiente. Solo debe tenerse en cuenta que Euler no conocía la terminología moderna, no usó el término "gráfico", llamó al borde "puente" y al vértice - "área" o "letra" y no dibujó imágenes modernas de gráficos [23] .

• “Por lo tanto, se vuelve obvio que si es posible pasar por siete puentes, y cada uno de ellos exactamente una vez, entonces esta ruta estará representada por ocho letras”.
• “... He desarrollado una regla por la cual uno puede decidir fácilmente, tanto para este problema como para todos los problemas similares, si se puede llevar a cabo tal disposición de letras.

8. Para derivar tal regla, considero un área específica a la que puede conducir un número arbitrario de puentes , etc. A partir de estos puentes, primero consideraré un puente específico que conduce al área . Si un viajero cruza este puente, o estaba en el área antes de cruzar este puente, o estará en el área después de eso. Por lo tanto, para designar este paso sobre el puente, como se ha descrito anteriormente, es necesario que la letra aparezca una vez .

• “Si tres puentes conducen al área, por ejemplo , y el viajero pasa por los tres puentes, entonces la letra aparecerá en la descripción de su movimiento en los puentes dos veces, independientemente de si su ruta comenzó o no. De la misma manera, si hay cinco puentes que conducen al área, entonces la letra debe aparecer tres veces al describir su movimiento. Y cuando el número de puentes es un número impar arbitrario, si lo aumenta en uno, la mitad del número resultante muestra cuántas veces debe aparecer la letra .
• 9. Por lo tanto, en el caso de los puentes de Königsberg, dado que cinco puentes conducen a la isla , es necesario que la letra aparezca tres veces en la descripción del movimiento a lo largo de estos puentes. Además, la letra debe encontrarse dos veces , ya que hay tres puentes que conducen al área, y las letras deben encontrarse dos veces cada una. Por tanto, en una secuencia de ocho letras que describe la ruta en cuestión, pasando por siete puentes, la letra debe aparecer tres veces, y cada una de las letras dos veces. Esto, sin embargo, no puede estar en una secuencia de ocho letras. Por lo tanto, está claro que tal paseo por los siete puentes de Königsberg es imposible”.

Generalización de la solución del problema

Resolviendo el problema en términos generales, Leonhard Euler demostró en el camino que para cualquier gráfico, el número de vértices con un número impar de aristas es par [24] :

• “Primero notaré que todos los números de puentes” que conducen a la región, “sumados juntos, dan el doble del número de todos los puentes. La razón es que cada puente se cuenta dos veces en esta cuenta, de modo que se cuentan todos los puentes que conducen a un área determinada, ya que cada puente conduce a las dos áreas que conecta.

17. De esta observación se sigue que la suma [de los números] de todos los puentes que conducen a cada región es un número par, ya que la mitad de esta suma es exactamente el número de puentes. Por lo tanto, no puede suceder que entre la cantidad de puentes que conducen a cualquier área, exactamente uno sea impar; tampoco puede ocurrir que haya tres, cinco, etc., de números impares, por tanto, si el número de puentes" que conducen a la región, "son números impares, su suma es par".

Al final del artículo, Leonhard Euler escribió las conclusiones generales para cualquier gráfico en un lenguaje bastante moderno [24] :

20. Por lo tanto, en todos los casos posibles, la siguiente regla permite saber directamente y sin dificultad si es posible realizar una caminata sobre todos los puentes sin repetición:

Si hay más de dos áreas a las que conducen un número impar de puentes, se puede decir con certeza que tal caminata es imposible.

Sin embargo, si solo hay dos regiones a las que conduce un número impar de puentes, entonces la caminata es factible, siempre que comience en una de estas dos regiones.

Si, finalmente, no existe una zona a la que conduzcan un número impar de puentes, es factible un paseo con las condiciones requeridas, pudiendo iniciarse en cualquier zona.

Por lo tanto, con la ayuda de esta regla, el problema planteado puede resolverse por completo.

— Leonard Euler. Resolviendo un problema relacionado con la geometría de posición

Véase también

• El problema del movimiento del caballo
• Teoría de grafos
• ciclo de euler
• Topología
• Puentes de Kaliningrado
• El problema del viajante de comercio

Notas

1. ↑ 1 2 Harari Frank. Teoría de Grafos, 2003 , p. 13
2. ↑ 1 2 3 4 Gráficos de Fleischner G. Euler y temas relacionados, 2002 , p. once.
3. ↑ 1 2 3 Frich R., Peregud E. E., Matsievsky S. V. Capítulos seleccionados de teoría de grafos, 2008 , p. una.
4. ↑ Gráficos de Fleischner G. Euler y temas relacionados, 2002 , p. 17
5. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736 , p. 129.
6. ↑ Teoría de grafos de Frank Harary , 2007 , p. una.
7. ↑ Problema del puente de Königsberg // Britannica .
8. ↑ Frich R., Peregud E. E., Matsievsky S. V. Capítulos seleccionados de teoría de grafos, 2008 , p. vii.
9. ↑ Denes Konig. Theorie der endlichen und unendlichen Graphen, 1936 , s. 24
10. ↑ Frich R., Peregud E. E., Matsievsky S. V. Capítulos seleccionados de teoría de grafos, 2008 , p. ix.
11. ↑ Frich R., Peregud E. E., Matsievsky S. V. Capítulos seleccionados de teoría de grafos, 2008 , p. 151.
12. ↑ 1 2 3 4 5 6 7 8 9 10 11 Gribkovskaia I., Halskau Ø., Laporte G. Los puentes de Königsberg, 2007 .
13. ↑ Ore O. Gráficos y su aplicación, 1965 , p. 6.
14. ↑ 1 2 3 4 Gráficos de Fleischner G. Euler y temas relacionados, 2002 , p. 26
15. ↑ Actas de las reuniones de la Conferencia de la Academia Imperial de Ciencias de 1725 a 1803. Volumen I. 1725-1743, 1897 , pág. 220-221.
16. ↑ 1 2 3 Gráficos de Fleischner G. Euler y temas relacionados, 2002 , p. quince.
17. ↑ Cartas a los científicos, 1963 , p. 152-158.
18. ↑ Cartas a los científicos, 1963 , p. 330-353.
19. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736 .
20. ↑ Ore O. Gráficos y su aplicación, 1965 , p. 33.
21. ↑ Frich R., Peregud E. E., Matsievsky S. V. Capítulos seleccionados de teoría de grafos, 2008 , p. cuatro
22. ↑ 1 2 3 4 Frich R., Peregud E. E., Matsievsky S. V. Capítulos seleccionados de teoría de grafos, 2008 , p. 8-12.
23. ↑ 1 2 Gráficos de Fleischner G. Euler y temas relacionados, 2002 , p. 27-28.
24. ↑ 1 2 Gráficos de Fleischner G. Euler y temas relacionados, 2002 , p. 31-32.

Literatura

• Ore O. Gráficos y su aplicación / Per. De inglés. L. I. Golovina. ed. I. M. Yagloma. M.: Mir, 1965. 174 p.: il.
• Actas de las reuniones de la Conferencia de la Academia Imperial de Ciencias de 1725 a 1803. Volumen I. 1725-1743 / Procès-verbaux des l'Académie Impériale des Sciences depuis sa fondation jusqu'à 1803. San Petersburgo: Imprenta IAN, 1897. 883 p.
• Harary Frank. Teoría de grafos / Per. De inglés. V. P. Kozyreva. ed. G. P. Gavrilova. 2ª edición. M.: Editorial URSS, 2003. 296 p.: il. ISBN 5-354-00301-6 .
• Gráficos de Fleishner G. Euler y temas relacionados. M.: Mir, 2002. 335 p.: il. ISBN 5-03-003115-4 (ruso). ISBN 0-444-88395-9 . [Fleischner H. Eulerian Graphs and Related Topics. P. 1, V. 1. Ámsterdam: Holanda Septentrional, 1990.]
• Frich R., Peregud E. E., Matsievsky S. V. Capítulos seleccionados de teoría de grafos: libro de texto / Per. con él. E. E. Pereguda; Pablo ed. S. V. Matsievsky. Kaliningrado: Editorial de la Universidad Estatal Rusa. I. Kant, 2008. 192 p.: il. ISBN 978-5-88874-880-0 .
• Leonardo Euler. Cartas a los científicos / Ed. Académico V. I. Smirnov . - Moscú-Leningrado: Editorial de la Academia de Ciencias de la URSS , 1963. Contiene el texto original en latín de las cartas y la traducción al ruso de Yu. Kh. Kopelevich (carta a Marinoni) y T. A. Lukina (carta a Eler).
• Problema del puente de Konigsberg // Britannica. * Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis // Commentarii Academiae Scientiarum Petropolitanae. 8 (1736) 1741, 128–140.
• Gribkovskaia I., Halskau Ø., Laporte G. Los puentes de Königsberg: una perspectiva histórica // ​​Redes. 2007. 49(3):199–203.
• Teoría de grafos de Frank Harary . Reading, Massachusetts: Addison-Wesley Publishing Company, 1969. 283 p.
• Denes Konig. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Leipzig: Akademische Verlagsgesellschaft MBH, 1936.

diccionarios y enciclopedias	Gran danés Britannica (en línea)