Los siete puentes de Königsberg son un problema histórico notable en matemáticas. Su resolución negativa por parte de Leonhard Euler en 1736 [1] sentó las bases de la teoría de grafos y prefiguró la idea de topología . [2]
La ciudad de Königsberg en Prusia (ahora Kaliningrado , Rusia ) estaba situada a ambos lados del río Pregel e incluía dos grandes islas, Kneiphof y Lomse , que estaban conectadas entre sí y con las dos partes continentales de la ciudad, por siete puentes. El problema era idear un paseo por la ciudad que cruzara cada uno de esos puentes una vez y sólo una vez.
A modo de especificar la tarea lógica sin ambigüedades, las soluciones que involucran
son explícitamente inaceptables.
Euler demostró que el problema no tiene solución. La dificultad que enfrentó fue el desarrollo de una técnica de análisis adecuada , y de pruebas posteriores que establecieran esta afirmación con rigor matemático.
Euler fue el primero en señalar que la elección de la ruta dentro de cada masa de tierra es irrelevante y que 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, se reemplaza cada masa de tierra con un " vértice " o nodo abstracto, y cada puente con una conexión abstracta, un " borde ", que sólo sirve para registrar qué par de vértices (masas de tierra) está conectado por ese puente. La estructura matemática resultante es una gráfica .
→
→
Dado que sólo 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í. Sólo el número de aristas (posiblemente cero) entre cada par de nodos es significativo. Por ejemplo, no importa si los bordes dibujados son rectos o curvos, o si un nodo está a la izquierda o a la derecha de otro.
A continuación, Euler observó que (excepto en los puntos finales del recorrido), siempre que uno entra en un vértice por un puente, sale del vértice por un puente. En otras palabras, durante cualquier recorrido por el gráfico, 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 deduce que, para cada masa de tierra (excepto los elegidos para la salida y la llegada), el número de puentes que tocan esa masa de tierra debe ser par (la mitad de ellos, en el determinado recorrido, será atravesado "hacia" la masa continental; 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, como máximo, dos masas de tierra pueden servir como puntos finales de un paseo, la proposición de que un paseo atraviese cada puente una vez conduce a una contradicción.
En lenguaje moderno, Euler muestra que la posibilidad de recorrer un gráfico, 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 recorrido de la forma deseada es que el gráfico sea conexo y tenga exactamente cero o dos nodos de grado impar. Esta condición también resulta suficiente, resultado afirmado por Euler y posteriormente demostrado por Carl Hierholzer . Este tipo de 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 que también tenga el mismo punto inicial y final. Este tipo de paseo se denomina circuito euleriano o recorrido de Euler . Tal circuito existe si, y sólo si, el gráfico está conexo y todos los nodos tienen grados pares. 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 la posición) en la revista Commentarii academiae scientiarum Petropolitanae en 1741. [3] Está disponible en traducción al inglés en The World of Mathematics de James R. Newman .
En la historia de las matemáticas , la solución de Euler al 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, [4] un tema ahora generalmente considerado como una rama de la combinatoria . Desde la antigüedad se habían considerado problemas combinatorios de otros tipos.
Además, el reconocimiento de Euler de que la información clave era el número de puentes y la lista de sus puntos finales (en lugar de sus posiciones exactas) presagió 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 ocupa de la forma rígida de los objetos.
Por tanto, como reconoció Euler, la "geometría de posición" no se trata de "medidas y cálculos" sino de algo más general. Esto puso en duda la visión tradicional aristotélica de que las matemáticas son la "ciencia de la cantidad ". Aunque esa visión se ajusta a la aritmética y a la geometría euclidiana, no se ajusta a la topología ni a las características estructurales más abstractas que se estudian en las matemáticas modernas. [5]
Los filósofos han observado que la demostración 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 tanto, la certeza de la prueba matemática puede aplicarse directamente a la realidad. [6] La prueba también es explicativa y da una idea de por qué el resultado debe ser verdadero. [7]
Dos de los siete puentes originales no sobrevivieron al bombardeo de Königsberg en la Segunda Guerra Mundial . Posteriormente, otros dos fueron demolidos y reemplazados por una carretera. Los otros tres puentes permanecen, aunque sólo dos de ellos son de la época de Euler (uno fue reconstruido en 1935). [8] Así, a partir de 2023 [actualizar], 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. [9]
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. [10] Los ríos son reemplazados por 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 campo de hockey sobre hielo que se inauguró en 2014, [11] y el Instituto de Tecnología de Georgia también instaló un modelo de arte paisajístico de los siete puentes en 2018. [12]
Una variante popular del rompecabezas es el Bristol Bridges Walk . [13] Al igual que el histórico Königsberg, Bristol ocupa dos riberas y dos islas fluviales. [14] Sin embargo, la configuración de los 45 puentes principales de Bristol es tal que existe un circuito euleriano. [15] Este ciclo se ha popularizado a través de un libro [15] y cobertura periodística [16] [17] y ha aparecido en diferentes eventos benéficos. [18]
