Los siete puentes de Königsberg es un problema históricamente notable en matemáticas. Su resolución negativa por Leonhard Euler , en 1736, [1] sentó las bases de la teoría de grafos y prefiguró la idea de la topología . [2]
La ciudad de Königsberg en Prusia (hoy 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 sola vez.
Para especificar la tarea lógica de forma inequívoca, se proponen soluciones que involucren cualquiera de las dos:
son explícitamente inaceptables.
Euler demostró que el problema no tiene solución. La dificultad a la que se enfrentó fue el desarrollo de una técnica adecuada de análisis y de posteriores pruebas 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, una " arista ", 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 grafo .
→
→
Como sólo es relevante la información de conexión, la forma de las representaciones gráficas de un gráfico puede distorsionarse de cualquier manera, sin cambiar el gráfico en sí. Sólo es importante el número de aristas (posiblemente cero) entre cada par de nodos. No importa, por ejemplo, si las aristas dibujadas son rectas o curvas, 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 se entra en un vértice por un puente, se sale del vértice por un puente. En otras palabras, durante cualquier recorrido en 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 deduce que, para cada masa de tierra (excepto las elegidas 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, se atravesarán "hacia" la masa de tierra; la otra mitad, "alejándose" de ella). Sin embargo, las cuatro masas de tierra del problema original son tocadas por un número impar de puentes (una es tocada por 5 puentes, y cada una de las otras tres es tocada por 3). Dado que, como máximo, dos masas de tierra pueden servir como puntos finales de un recorrido, la proposición de un recorrido que atraviese cada puente una vez conduce a una contradicción.
En lenguaje moderno, Euler muestra que la posibilidad de un paseo a través de un grafo, recorriendo cada arista 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 paseo 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 posteriormente demostrado por Carl Hierholzer . Este paseo se llama ahora camino euleriano o paseo de Euler en su honor. Además, si hay nodos de grado impar, entonces 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 de inicio y de finalización. Este tipo de recorrido se denomina circuito euleriano o recorrido de Euler . Este tipo de circuito existe si, y solo si, el grafo está conectado 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 en 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 demostración verdadera en la teoría de redes, [4] un tema que ahora se considera generalmente como una rama de la combinatoria . Los problemas combinatorios de otros tipos, como la enumeración de permutaciones y combinaciones , se habían considerado desde la antigüedad.
El reconocimiento por parte 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) 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 ocupa de la forma rígida de los objetos.
Por lo tanto, como reconoció Euler, la "geometría de la posición" no trata de "mediciones y cálculos", sino de algo más general. Esto puso en tela de juicio la visión aristotélica tradicional 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 ajustaba a la topología y a las características estructurales más abstractas que se estudian en las matemáticas modernas. [5]
Los filósofos han señalado que la prueba de Euler no se refiere a una abstracción o un modelo de la realidad, sino directamente a la disposición real de los puentes. Por lo tanto, la certeza de la prueba matemática puede aplicarse directamente a la realidad. [6] La prueba también es explicativa, y permite comprender 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 . Otros dos fueron demolidos posteriormente y reemplazados por una autopista. Los otros tres puentes permanecen, aunque solo dos de ellos son de la época de Euler (uno fue reconstruido en 1935). [8] Estos cambios dejan cinco puentes existentes 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 y Ciencias de la Computación. [10] 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 ha incorporado el rompecabezas en el pavimento frente al Centro Gene Polisseni , un estadio 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 orillas fluviales 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 mediante un libro [15] y la cobertura periodística [16] [17] y ha aparecido en diferentes eventos benéficos. [18]
