Cómo los siete puentes de Königsberg generaron nuevas matemáticas

Durante el siglo XVIII, los habitantes de la ciudad prusiana de Königsberg lucharon con un enigma: ¿Cómo podrían encontrar un sendero para caminar a través de la ciudad que cruzara cada uno de sus siete puentes históricos exactamente una vez?

Los puentes cruzaban un río que contenía dos grandes islas. Por mucho que diseñaran estrategias para sus rutas, no podían evitar repetir un puente.

El problema obstaculizó a los pensadores locales, quienes finalmente escribieron una carta a el famoso matemático Leonhard Euler (pronunciado “engrasador”) rogándole que descanse su curiosidad. Euler respondió con desdén, afirmando que el problema tenía “poca relación con las matemáticas”. En cierto modo, tenía razón, porque las matemáticas relevantes aún no se habían inventado. A pesar de su objeción inicial, Euler acabó resolviendo el enigma de los siete puentes de Königsberg, sin saber que en el proceso había dado origen a dos nuevos. ramas de las matemáticas.

Sobre el apoyo al periodismo científico

Si está disfrutando este artículo, considere apoyar nuestro periodismo galardonado al suscribiéndose. Al comprar una suscripción, ayudas a garantizar el futuro de historias impactantes sobre los descubrimientos y las ideas que dan forma a nuestro mundo actual.

Digamos que usted reside en Königsberg. Mirando el mapa de arriba, ¿podrías diseñar un camino que atraviese cada puente una vez? Tendrás que pensar como un matemático. El primer obstáculo al resolver cualquier problema matemático es eliminar la información superflua hasta que sólo queden los elementos esenciales. un proceso llamado abstracción. Muchas características del mapa no afectan la pregunta en cuestión. Se pueden descartar las longitudes de los puentes, los tamaños de las masas de tierra e incluso la orientación geográfica del terreno y de los puentes. Lo único que importa es qué terrenos se conectan con otros y cuántas veces. Ahora podemos crear un diagrama mucho más simple que consta únicamente de círculos y líneas para representar terrenos y puentes, respectivamente.

El lenguaje matemático moderno lo llama “gráfico”, que no debe confundirse con otros gráficos matemáticos no relacionados, como los gráficos en el plano xy o visualizaciones estadísticas como los gráficos de barras. Quizás “red” hubiera sido un término mejor para evitar confusiones. Llamamos a los círculos “vértices” y a las líneas “bordes”. Hoy en día, la teoría de grafos es un área importante de las matemáticas y la informática con una amplia gama de aplicaciones. Los gráficos no tienen por qué representar tierras y puentes. pueden representar redes socialesinteracciones de proteínas, fronteras estatalesredes neuronales, la World Wide Web o cualquier otro dato que implique relaciones por pares.

La abstracción permite a los matemáticos traducir un problema muy específico sobre una disposición particular de puentes en una ciudad antigua a un problema general sobre todas las gráficas. Dado un gráfico con cualquier número de vértices y aristas, ¿existe un camino que atraviese cada arista exactamente una vez? Resulta que una prueba increíblemente simple puede responder esto para cualquier gráfico: para cada vértice (masa de tierra en nuestro rompecabezas actual), cuente el número de aristas (puentes) que emanan de él. Si todos esos conteos son números pares, o si todos menos dos son pares, entonces el camino existe; de lo contrario, el camino es imposible.

Exploremos el razonamiento. Imagine un camino a través de un gráfico que cruza cada borde una vez. Considere un vértice en el medio de ese camino (no el vértice inicial o final). Si ese vértice tiene muchas aristas, entonces su camino lo visitará varias veces, pero cada vez que ingrese al vértice, también deberá salir por una arista diferente. Entonces, cada vez que se visita un vértice en el medio del camino, dos Los bordes son visitados. Eso sólo funciona si cada vértice en el medio del camino tiene un número par de aristas. El inicio y el final de la ruta son las únicas excepciones, porque no es necesario ingresar el vértice inicial y no es necesario salir del vértice final. Entonces, si tenemos exactamente dos vértices con un número impar de aristas, entonces nuestro camino es posible si comienza y termina en esos vértices. Si cada vértice tiene un número par de aristas, entonces habrá un camino que comienza y termina en el mismo vértice formando un bucle.

Este argumento se considera el primer resultado en Teoría de grafosy las rutas a través de gráficos que visitan cada borde una vez ahora se llaman Caminos eulerianos. Técnicamente, el argumento de Euler describe sólo las condiciones que hacen imposible un camino euleriano, y la prueba de que tal camino siempre existe bajo estas condiciones llegó más tarde. Aplicando lo que hemos aprendido a los puentes de Königsberg, vemos que los cuatro vértices tienen un número impar de aristas que emanan de ellos, lo que significa, por desgracia, que los caminantes prusianos buscaron en vano.

Aquí hay una nota al margen peculiar. Encontrar un camino a través de un gráfico que visite cada vértice (la tierra en lugar de los puentes en nuestro ejemplo) exactamente una vez suena como un problema estrechamente relacionado, pero en realidad es una bestia completamente diferente. Aunque una prueba simple puede determinar si un gráfico contiene una trayectoria euleriana, no conocemos ningún procedimiento general eficiente para esta variante centrada en los vértices. Esta variante se llama problema de la trayectoria hamiltoniana y pertenece a una clase de problemas que se cree ampliamente que son computacionalmente intratable.

Aunque Euler inicialmente se burló del problema del puente, finalmente se sintió atraído por su incapacidad para resolverlo con su kit de herramientas habitual. Le escribió a un amigo: “Esta cuestión es muy banal, pero me pareció digna de atención porque ni la geometría, ni el álgebra, ni siquiera el arte de contar eran suficientes para resolverla”. En aquella época, la geometría se refería a nociones cuantitativas como distancia, ángulo y área. Pero si bien el problema del puente parecía de naturaleza geométrica, no requería ningún tipo de medición. El problema requería una nueva abstracción que ignorara las cantidades geométricas tradicionales, respetando al mismo tiempo las conexiones por pares en el centro de la pregunta.

La idea de reducir el mapa de Königsberg a un gráfico básico puede parecer obvia en retrospectiva, pero muchas de las mejores abstracciones lo son. La historia de las matemáticas cuenta la historia del poder de la abstracción. Si las mentes matemáticas antiguas tuvieran preguntas cuantitativas sobre las naranjas, las perlas o incluso la Tierra, podrían desarrollar un lenguaje y técnicas a medida para abordar cada nuevo desafío. Pero el esfuerzo se vuelve mucho más fácil y claro una vez que uno reconoce que todos estos objetos de apariencia dispar representan la misma entidad de orden superior: una esfera. Darle a la abstracción un nombre y una definición permite a personas que ni siquiera se han conocido construir sobre el trabajo de los demás sin reinventar la rueda.

El artículo de Euler no sólo lanzó el campo de la teoría de grafos, sino que también sembró las semillas de otra importante rama de las matemáticas llamada topología. La topología se refiere al estudio de las propiedades geométricas que persisten incluso cuando estiramos, comprimimos o deformamos objetos como si estuvieran hechos de caucho altamente elástico. Entonces, mientras un nivel de abstracción nos llevó de objetos del mundo real como naranjas, montañas y dados a sus formas (esferas, pirámides y cubos), la topología introduce un segundo nivel de abstracción en el que vemos esferas, pirámides y cubos como instancias de alguna entidad de orden aún superior. Los topólogos ven estos sólidos como equivalentes. porque cada uno puede ser moldeado en el otro en un mundo gomoso, a diferencia de una donaque mantendría un agujero sin importar cómo lo estiraras.

Al abstraer los detalles cuantitativos del mapa de Königsberg, Euler abrió la puerta a un nuevo tipo de pensamiento geométrico, liberado de los detalles cuantitativos de distancia y ángulo que habían dominado el tema durante milenios. La teoría de grafos y la topología continúan brindando nuevos conocimientos matemáticos hoy en día, y tenemos que agradecerle a una civilización pasada de vagabundos.