Seguramente todos los lectores han intentado resolver alguna vez acertijos matemáticos que aparentemente no tienen nada que ver con números como es el caso del conocido desafío consistente en unir un conjunto de puntos o vértices con un solo trazo, dibujando una sola vez cada línea entre un punto y otro, sin necesidad de levantar el lápiz.
El reto más ampliamente difundido, al que seguramente usted se ha enfrentado alguna vez es el del sobre cerrado o el del sobre abierto que se muestran en la figura:
Para el caso de la figura de la izquierda, el acertijo se conoce como del sobre cerrado y no es posible encontrar una solución, es decir no existe un camino que una todos los puntos (o solo los vértices), de un solo trazo.
En cambio para la figura de la derecha, del sobre abierto, sí es posible unir los puntos con un solo trazo (puede intentarlo ahora y encontrar una solución).
Este sencillo reto explica muy bien la manera como se puede, matemáticamente, demostrar o refutar una afirmación sobre la existencia de soluciones. Si no existe una solución al problema, hay que demostrar que así es en forma general, pero si se quiere refutarlo, basta encontrar y exhibir una solución; así se demuestra que existe al menos una.
Pero esta bonita entretención matemática del sobre abierto y del sobre cerrado conduce a una pregunta más general y difícil de responder: si no siempre puede unirse un conjunto de puntos bajo esas condiciones, entonces ¿cuándo se puede? La respuesta a esta inquietud aparentemente intrascendente dio origen, precisamente, a lo que hoy se conoce como Teoría de Grafos.
Y es que detrás de este tema hay una historia muy conocida, pero no por eso menos fascinante, sobre un curioso problema que se le planteó al famoso matemático suizo Leonard Euler en el año de 1735. El problema era el siguiente: la ciudad de Königsberg, que por aquella época pertenecía a Prusia, la misma que actualmente se llama Kaliningrado y pertenece a Rusia, conocida por su Universidad Albertina, fundada en 1544 y por ser la ciudad donde nació y pasó toda su vida el filósofo Immanuel Kant; era una ciudad que estaba atravesada por el río Pregel, que en la actualidad se denomina Pregolya. A su paso por la ciudad, este río formaba dos islas y para unir las cuatro partes separadas de la ciudad existían siete puentes, como lo muestra la imagen.
Era costumbre entre los habitantes de Königsberg dar un paseo los domingos y festivos tratando de recorrer las cuatro zonas de la ciudad, para lo cual era necesario cruzar todos los puentes, pero nadie había logrado hacerlo sin pasar al menos dos veces por el mismo puente. Fue así como el reto de resolver este conflictivo problema, objeto de apuestas frecuentes entre los lugareños y visitantes, se le planteó a Euler en la siguiente forma: ¿Es posible recorrer todas las zonas de la ciudad de Königsberg, atravesando todos los puentes, una y sólo una vez cada uno de ellos?
Euler encontró una solución ingeniosa, que hoy en día parece simple (como lo son la mayoría de las respuestas y soluciones a los problemas después de descubiertas) y presentó un trabajo en el que demostraba la imposibilidad de tal ruta. Posteriormente, en 1736, publicó un artículo titulado “Solutio problematis ad geometriam situs pertinentis”, en el que presentaba condiciones generales para la existencia de soluciones para cualquier problema del mismo tipo. Este artículo es considerado por varios autores como el nacimiento de la Teoría de Grafos, utilizada actualmente en una gran cantidad de aplicaciones.
La definición de grafo está inspirada en ese problema, un grafo es básicamente un conjunto no vacío (es decir que al menos contiene un elemento) de puntos llamados vértices y un conjunto de líneas llamadas aristas, cada una de las cuales une dos vértices. La idea de Euler fue representar la ciudad de Königsberg como un grafo en el que las cuatro partes de la misma eran los vértices y los siete puentes eran las aristas. Observó que por los vértices debe pasar un número par de aristas, para que por cada una que llegue haya otra que salga, cosa que no se cumplía en este grafo; así que la conclusión fue contundente: no se puede encontrar un camino que recorra todos los puentes de Königsberg, pasando por cada uno de ellos una vez solamente.
La teoría de grafos ha sido muy fértil en el planteamiento y solución de problemas de toda índole, así como en la producción de bellas ideas. Les comparto otro famoso problema relacionado, del mismo tipo: el conocido bajo el nombre de problema de los cuatro colores, planteado en 1852 por Francis Guthrie. El problema consiste en demostrar que es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países, de tal forma que dos países vecinos nunca tengan el mismo color.
Este problema fue resuelto un siglo después por Kenneth Appel y Wolfgang Haken. La demostración que ellos presentaron en 1976 no es habitual, pues se hizo con ayuda del computador, por esta razón algunos escépticos y otros fundamentalistas no aceptan esta prueba como una demostración válida.
Un ejemplo más es el interesante problema conocido como la “teoría de los seis grados de separación”, que intenta probar el dicho según el cual «el mundo es un pañuelo”. Se trata de demostrar que cualquier persona en el planeta puede estar conectada con otra persona a través de una cadena de conocidos que no tiene más de cinco intermediarios; es decir que dos personas cualesquiera sobre la Tierra pueden conectarse con solo seis enlaces a lo sumo. Es un bello problema que les compartiré y describiré más ampliamente en otro artículo.
Volviendo sobre los grafos, hay que saber que son una herramienta fundamental para el modelamiento matemático de las actuales dinámicas de las redes sociales y son aplicados especialmente en la construcción de algoritmos utilizados para la simulación en todo tipo de investigaciones propias de las ciencias de la computación, pero también han sido usados en problemas de tan diversas áreas como la investigación de operaciones, la lingüística, la genética, la sociología o la electricidad.
La reflexión que nos deja esta historia del problema de los puentes de Königsberg es sobre la importancia de aprender a resolver problemas, aun cuando aparentemente no tengan importancia o aplicación alguna. La idea que tuvo Euler se logró generalizar en una idea que originó nuevas herramientas, métodos, teorías e infinidad de aplicaciones impensables en esa época. Es por eso que debemos formar a nuestros estudiantes para que puedan despejar las nuevas incógnitas, especialmente aquellas que aún ni siquiera imaginamos.
@MantillaIgnacio