Siete puentes de Königsberg - Seven Bridges of Königsberg

Mapa de Königsberg en la época de Euler que muestra el diseño real de los siete puentes, destacando el río Pregel y los puentes.

Los siete puentes de Königsberg es un problema históricamente notable en matemáticas. Su resolución negativa de 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 ) se estableció a ambos lados del río Pregel e incluía dos grandes islas, Kneiphof y Lomse, que estaban conectadas entre sí, o 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 solo una vez.

A modo de especificar la tarea lógica de forma inequívoca, las soluciones que implican

  1. llegar a una isla o ribera continental que no sea a través de uno de los puentes, o
  2. Accediendo 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 de análisis adecuada , y de pruebas posteriores que establecieran esta afirmación con rigor matemático.

El análisis de Euler

Primero, Euler 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, se reemplaza cada masa de tierra con un " vértice " o nodo abstracto , 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 .

Puentes Konigsberg.png7 puentes.svgKönigsberg graph.svg

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.

A continuación, Euler observó que (excepto en los puntos finales de la caminata), siempre que uno entra en un vértice por un puente, uno abandona el vértice por un puente. En otras palabras, durante cualquier recorrido en el gráfico, el número de veces que uno entra en un vértice no terminal es igual al número de veces que lo abandona. Ahora bien, si cada puente ha sido atravesado exactamente una vez, se deduce 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 travesía particular, será atravesada "hacia" la masa de tierra; la otra mitad, "alejándose" de ella). Sin embargo, las cuatro masas de tierra en el problema original son tocadas por un número impar de puentes (uno es tocado por 5 puentes y cada uno de los otros tres es tocado por 3). Dado que, a lo sumo, dos masas de tierra pueden servir como puntos finales de un paseo, la proposición de un paseo que 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 bordes que lo tocan. El argumento de Euler muestra que una condición necesaria para la caminata de la forma deseada es que el gráfico esté conectado y tenga exactamente cero o dos nodos de grado impar. Esta condición también resulta ser suficiente, resultado enunciado por Euler y más tarde probado por Carl Hierholzer . Este camino se llama ahora camino euleriano o camino 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 gráfico correspondiente al histórico de Königsberg tiene cuatro nodos de grado impar, no puede tener una trayectoria euleriana.

Una forma alternativa del problema pide un camino que atraviese todos los puentes y que también tenga el mismo punto de inicio y final. Tal caminata se llama circuito euleriano o recorrido Euler . Tal circuito existe si, y solo si, el gráfico está conectado y no hay nodos de grado impar en absoluto. 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 pertinente (La solución de un problema relacionado con la geometría de la posición) en la revista Commentarii academiae scientiarum Petropolitanae en 1741. Está disponible en traducción al inglés en The World of Mathematics por 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 la combinatoria . Los problemas combinatorios de otros tipos se habían considerado desde la antigüedad.

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) 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 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 tela de juicio la visión aristotélica tradicional de que las matemáticas son la "ciencia de la cantidad ". Aunque ese punto de vista se ajusta a 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 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 demostración matemática puede aplicarse directamente a la realidad. La prueba también es explicativa y da una idea de por qué el resultado debe ser verdadero.

Estado actual de los puentes

Mapa moderno de Kaliningrado. Las ubicaciones de los puentes restantes se resaltan en verde, mientras que los destruidos se resaltan en rojo.
En esta imagen de la catedral de Königsberg , el puente de la derecha es uno de los dos puentes supervivientes de la época de Euler.

Dos de los siete puentes originales no sobrevivieron al bombardeo de Königsberg en la Segunda Guerra Mundial . Más tarde, otros dos fueron demolidos y reemplazados por una carretera moderna. Los otros tres puentes permanecen, aunque solo dos de ellos son de la época de Euler (uno fue reconstruido en 1935). Así, a partir de 2021, 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 son reemplazados por arbustos cortos y la isla central luce un torero 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.

Comparación de los gráficos de los siete puentes de Konigsberg (arriba) y el rompecabezas de cinco habitaciones (abajo). Los números denotan el número de bordes conectados a cada nodo. Los nodos con un número impar de bordes aparecen sombreados en naranja.

Ver también

Referencias

enlaces externos

Coordenadas : 54 ° 42′12 ″ N 20 ° 30′56 ″ E / 54.70333 ° N 20.51556 ° E / 54.70333; 20.51556