Las Voces de Ingenierías: La imposibilidad como medio de creación
12/08/2022
Autor: Dr. Damián Emilio Gibaja Romero
Foto: Área de Matemáticas

Al visitar una ciudad nueva por fines vacacionales, es común que busquemos maximizar el número de lugares por conocer. Por ende, al ir de un lugar turístico a otro, tratamos de hacer recorridos por calles distintas para conocer nuevos lugares o recorrer la ciudad completa sin visitar dos veces la misma atracción turística. 

En el siglo XVIII, Leonhard Euler quedó maravillado por la infraestructura de transporte de la ciudad de Königsberg, la actual ciudad rusa de Kaliningrado. Cuando Euler salía a caminar en dicha ciudad, observó que Königsberg estaba dividida en cuatro regiones debido a que un río la atravesaba. Entonces, los habitantes locales construyeron siete puentes para poder ir de una región a otra. Euler se preguntó si era posible visitar las cuatro regiones de la ciudad recorriendo cada puente sólo una vez. Después de reflexionar sobre el problema anterior, la respuesta resulta ser negativa. Es decir, no es posible recorrer la ciudad pasando por los puentes sólo una vez. 

Si decidimos utilizar la fuerza bruta, podemos llegar al resultado anterior descartando cada una de las opciones posibles. Sin embargo, Euler descubrió que el procedimiento anterior no era lo más conveniente y propuso una nueva herramienta matemática para encontrar analizar este tipo de problemas. Particularmente, Euler notó que cada región se puede representar por punto, o vértice, y que los puentes son aristas que unen los vértices. Es decir, entre vértices hay una arista sí y sólo si existe un puente que comunique a las regiones que representan dichos nodos. 

Al usar vértices y aristas, la ciudad de Königsberg se pudo abstraer a una red, representación que también se denomina grafo o gráfica cuando es posible caminar en ambas direcciones por la arista. De esta manera, recorrer a la ciudad sin pasar dos veces por el mismo puede entenderse como la búsqueda de una sucesión de aristas (un camino o trayectoria) donde las aristas no se repiten y se pasa por todos los vértices. Euler estableció que es posible encontrar las trayectorias anteriores cuando la red tiene exactamente dos grados de impar; es decir, cuando hay exactamente dos regiones sobre las que se puede llegar por medio de tres puentes. Por la importancia y novedad de este resultado, al camino buscado se le nombró como camino euleriano

La búsqueda de caminos eulerianos ha tenido un impacto muy grande en el desarrollo de las matemáticas aplicadas. Más allá de establecer un resultado de imposibilidad, se creó la Teoría de Gráficas con la cual se pueden estudiar estructuras discretas generadas por problemas combinatorios. Así, encontramos aplicaciones de esta teoría tanto en las ciencias de la computación, para prevenir ataques cibernéticos en redes digitales, como en la logística, con el problema del agente viajero. En este último se busca minimizar la distancia recorrida de un agente que quiere visitar una serie de lugares llegando al mismo lugar de donde se partió.