Siete puentes de Königsberg
Los Siete Puentes de Königsberg es un problema matemático históricamente notable. Su resolución negativa por Leonhard Euler en 1736 sentó las bases de la teoría de grafos y prefiguró la idea de topología.
La ciudad de Königsberg en Prusia (ahora Kaliningrado, Rusia) estaba ubicada a ambos lados del río Pregel e incluía dos islas grandes, Kneiphof y Lomse, que estaban conectadas entre sí y con las dos partes continentales del río Pregel. ciudad, por siete puentes. El problema era idear un paseo por la ciudad que cruzara cada uno de esos puentes una sola vez.
A modo de especificar la tarea lógica sin ambigüedades, las soluciones que implican
- llegar a una isla o a un banco continental que no sea a través de uno de los puentes, o
- acceso a cualquier puente sin cruzar a su otro extremo
son explícitamente inaceptables.
Euler demostró que el problema no tiene solución. La dificultad que enfrentó fue el desarrollo de una técnica adecuada de análisis y de pruebas posteriores que establecieran esta afirmación con rigor matemático.
Análisis de Euler
Euler primero señaló que la elección de la ruta dentro de cada masa de tierra es irrelevante. La única característica importante de una ruta es la secuencia de puentes cruzados. Esto le permitió reformular el problema en términos abstractos (sentando las bases de la teoría de grafos), eliminando todas las características excepto la lista de masas de tierra y los puentes que las conectan. En términos modernos, uno reemplaza cada masa de tierra con un "vértice" abstracto. o nodo, y cada puente con una conexión abstracta, un 'borde', que solo sirve para registrar qué par de vértices (masas de tierra) está conectado por ese puente. La estructura matemática resultante es un gráfico.
→
→
Dado que solo la información de conexión es relevante, la forma de las representaciones pictóricas de un gráfico puede distorsionarse de cualquier manera, sin cambiar el gráfico en sí. Solo la existencia (o ausencia) de un borde entre cada par de nodos es significativa. Por ejemplo, no importa si los bordes dibujados son rectos o curvos, o si un nodo está a la izquierda oa la derecha de otro.
Luego, Euler observó que (excepto en los puntos finales de la caminata), cada vez que uno ingresa a un vértice por un puente, uno sale del vértice por un puente. En otras palabras, durante cualquier recorrido por el grafo, el número de veces que se entra en un vértice no terminal es igual al número de veces que se sale de él. Ahora bien, si cada puente ha sido atravesado exactamente una vez, se sigue que, para cada masa de tierra (excepto los elegidos para el inicio y el final), el número de puentes que tocan esa masa de tierra debe ser par (la mitad de ellos, en el recorrido particular, serán atravesados 'hacia' la masa de tierra; la otra mitad, 'alejándose' de ella). Sin embargo, las cuatro masas de tierra del problema original están tocadas por un número impar de puentes (uno está tocado por 5 puentes y cada uno de los otros tres está tocado por 3). Dado que, a lo sumo, dos masas de tierra pueden servir como puntos finales de una caminata, la proposición de una caminata que atraviesa cada puente una vez conduce a una contradicción.
En lenguaje moderno, Euler muestra que la posibilidad de recorrer un grafo, atravesando cada borde exactamente una vez, depende de los grados de los nodos. El grado de un nodo es el número de aristas que lo tocan. El argumento de Euler muestra que una condición necesaria para el camino de la forma deseada es que el grafo sea conexo y tenga exactamente cero o dos nodos de grado impar. Esta condición también resulta ser suficiente, un resultado establecido por Euler y luego probado por Carl Hierholzer. Tal paseo ahora se llama camino euleriano o paseo de Euler en su honor. Además, si hay nodos de grado impar, cualquier camino euleriano comenzará en uno de ellos y terminará en el otro. Dado que el grafo correspondiente al Königsberg histórico tiene cuatro nodos de grado impar, no puede tener un camino euleriano.
Una forma alternativa del problema pide un camino que atraviese todos los puentes y también tenga el mismo punto de inicio y final. Este paseo se llama circuito euleriano o recorrido euleriano. Tal circuito existe si, y solo si, el grafo es conexo y todos los nodos tienen un grado par. Todos los circuitos eulerianos son también caminos eulerianos, pero no todos los caminos eulerianos son circuitos eulerianos.
El trabajo de Euler fue presentado a la Academia de San Petersburgo el 26 de agosto de 1735 y publicado como Solutio problematis ad geometriam situs pertinentis (La solución de un problema relacionado con la geometría de posición) en la revista Commentarii academiae scientiarum Petropolitanae en 1741. Está disponible en traducción al inglés en The World of Mathematics de James R. Newman.
Importancia en la historia y filosofía de las matemáticas
En la historia de las matemáticas, la solución de Euler del problema del puente de Königsberg se considera el primer teorema de la teoría de grafos y la primera prueba verdadera en la teoría de redes, un tema que ahora se considera generalmente como una rama de combinatoria. Desde la antigüedad se habían considerado problemas combinatorios de otro tipo.
Además, el reconocimiento de Euler de que la información clave era el número de puentes y la lista de sus extremos (en lugar de sus posiciones exactas) presagiaba el desarrollo de la topología. La diferencia entre el diseño real y el esquema gráfico es un buen ejemplo de la idea de que la topología no se preocupa por la forma rígida de los objetos.
Por lo tanto, como reconoció Euler, la "geometría de la posición" no se trata de "medidas y cálculos" sino de algo más general. Eso puso en duda la visión aristotélica tradicional de que las matemáticas son la "ciencia de la cantidad". Aunque ese punto de vista encaja con la aritmética y la geometría euclidiana, no encajaba con la topología y las características estructurales más abstractas estudiadas en las matemáticas modernas.
Los filósofos han notado que la prueba de Euler no se trata de una abstracción o un modelo de la realidad, sino directamente de la disposición real de los puentes. Por lo tanto, la certeza de la prueba matemática puede aplicarse directamente a la realidad. La prueba también es explicativa, dando una idea de por qué el resultado debe ser verdadero.
Estado actual de los puentes
Dos de los siete puentes originales no sobrevivieron al bombardeo de Königsberg en la Segunda Guerra Mundial. Otros dos fueron demolidos más tarde y reemplazados por una carretera moderna. Quedan los otros tres puentes, aunque solo dos de ellos son de la época de Euler (uno fue reconstruido en 1935). Por lo tanto, a partir de 2022, existen cinco puentes en los mismos sitios que estuvieron involucrados en el problema de Euler. En términos de teoría de grafos, dos de los nodos ahora tienen grado 2 y los otros dos tienen grado 3. Por lo tanto, ahora es posible un camino euleriano, pero debe comenzar en una isla y terminar en la otra.
La Universidad de Canterbury en Christchurch ha incorporado un modelo de los puentes en un área de césped entre la antigua Biblioteca de Ciencias Físicas y el Edificio Erskine, que alberga los Departamentos de Matemáticas, Estadística e Informática. Los ríos se reemplazan con arbustos cortos y la isla central luce un tōrō de piedra. El Instituto de Tecnología de Rochester incorporó el rompecabezas en el pavimento frente al Centro Gene Polisseni, un estadio de hockey sobre hielo que se inauguró en 2014, y el Instituto de Tecnología de Georgia también instaló un modelo de arte paisajístico de los siete puentes en 2018.
