viernes, 18 de julio de 2025

¿Qué es la teoría de grafos?

¿Cómo calcula Google Maps cuál es la ruta más rápida para que vayas hasta la playa? ¿Cómo sabe Netflix qué serie recomendarte? Todo está interconectado. La teoría de grafos es la rama de las matemáticas que estudia estas conexiones. En este post, hablaremos sobre lo que es la teoría de grafos y daremos solución al acertijo de ayer. Sigue leyendo para descubrirla.

Lo primero de todo, ¿qué es un grafo? Imagina un conjunto de puntos, a los que llamaremos vértices (o nodos) y líneas que los unen, que se llaman aristas. Eso es un grafo. Dependiendo de la complejidad, un grafo puede representar relaciones del mundo real. Por ejemplo, si los vértices son ciudades y las aristas son carreteras, tenemos una representación de un mapa de carreteras, que nos indica qué ciudades están conectadas con qué ciudades. También podríamos representar relaciones de amistad, con las personas como vértices y las aristan conectan a los amigos. O incluso podría servirnos para hablar de moléculas y los enlaces químicos que existen entre ellas.

Existen distintos tipos de grafos: algunos tienen aristas que solo van en una dirección (como las calles de sentido único), y esos los llamamos grafos dirigidos. Otros pueden tener múltiples aristas entre los mismos dos vértices, o incluso aristas que conectan un vértice consigo mismo. O también podemos darles "pesos" a las aristas, es decir, algo así como costes por pasar por esa línea (piensa, por ejemplo, en un grafo que represente una red de autopistas de peaje) ¡La versatilidad es enorme!

El origen de toda esta teoría es una historia muy curiosa que siempre se cuenta el primer día de clase y que corresponde al acertijo del anterior post. En el siglo XVIII, la ciudad de Königsberg, en Prusia, estaba dividida por el río Pregel y contaba con siete puentes que conectaban las distintas orillas e islas del río. La gente de Königsberg tenía un acertijo popular: ¿era posible dar un paseo comenzando desde cualquier punto de la ciudad y cruzando cada uno de los puentes exactamente una vez? Muchos lo intentaron, pero nadie parecía ser capaz de llegar a la solución. Hasta que, en 1736, un brillante matemático suizo llamado Leonard Euler decidió abordar el problema.


Euler, en lugar de dibujar los puentes y las islas, tuvo una idea revolucionaria: simplificó el problema y representó cada una de las cuatro masas de tierra como un punto (vértice) y cada puente como una línea (arista) que conectaba esos puntos. Observa un momento las dos imágenes y comprueba que representan el mismo problema.


Al hacer esto, Euler se dio cuenta de algo sorprendente: ¡no era posible realizar tal paseo por la ciudad! Demostró que, para que tal recorrido fuera posible (lo que hoy conocemos como un camino euleriano o circuito euleriano), cada vértice del grafo debía tener un número par de aristas (puentes) conectadas a él, o a lo sumo dos vértices con un número impar de aristas. En el caso de Königsberg, todos los vértices tenían un número impar de puentes. ¿Por qué un número par? Fijémonos por ejemplo, en la orilla superior, el área C. ¿Ves que de aquí salen tres puentes/aristas? Este vértice tendrá que ser por fuerza uno de los extremos del camino (o el inicio o el final), porque, de lo contrario, pasaríamos a través de esta región "gastando" dos puentes (uno para entrar y otro para salir) y nos quedaría un solo puente para más adelante. Entraríamos y ya no podríamos volver a salir de aquí. En resumen, concluimos que el vértice C tiene que ser uno de los extremos. Ay, pero fíjate ahora en el vértice B, la orilla inferior. ¡También ocurre lo mismo, tiene tres aristas! Qué fácil, ahora ya sabemos que nuestro camino empieza en C y acaba en B, o al revés. Pero aquí es donde viene el problema... El vértice D TAMBIÉN tiene tres vértices. Y, lo que es peor, el vértice A tiene cinco aristas, le ocurre más de lo mismo. Nuestro camino no puede tener cuatro extremos distintos, ¿no? Es porque es imposible y no existe un camino que contente a los habitantes de Königsberg para sus paseos.

Como curiosidad, el argumento que empleó Euler para resolver este problema lo puedes utilizar para acertijos del tipo "¿Puedes dibujar esta figura sin levantar el lápiz del papel?" (como los que puedes encontrar AQUÍ). Para que sea posible, el dibujo tiene que tener, a lo sumo, dos vértices con un número impar de aristas. Si tiene más, ocurre igual que en Königsberg. Así, es rápido identificar los vértices impares y empezar desde allí a dibujar.

¡Y así, sin saberlo, Euler sentó las bases de la Teoría de Grafos! Con el tiempo, esta rama se ha desarrollado y ahora se emplea en muchas otras áreas de las matemáticas u otras ciencias. Por ejemplo, en 1845, Gustav Kirchhoff utilizó la teoría de grafos para analizar circuitos eléctricos. En 1852, apareció un problema que se convertiría en un clásico en el campo de la cartografía (y creo recordar que en algún examen de la carrera me pidieron demostrar alguna versión): el problema de los Cuatro Colores. Francis Guthrie, mientras coloreaba un mapa de condados de Inglaterra, notó que solo necesitaba cuatro colores para asegurarse de que dos condados adyacentes tuvieran colores diferentes. ¿Bastan cuatro colores para pintar cualquier mapa de forma que dos regiones distintas tengan colores distintos? Esta conjetura no se probó hasta 1976, ¡más de un siglo después!

Hoy en día, la teoría de grafos tiene aplicaciones en casi todos los campos imaginables:

  • Informática: el funcionamiento de internet, las redes sociales (Instagram, LinkedIn), los algoritmos de búsqueda (Google Maps para encontrar la ruta más corta, Netflix para recomendarte series). La World Wide Web es un grafo gigante, donde las páginas web son vértices y los enlaces, aristas.

  • Logística: optimización de rutas de entrega para empresas de paquetería o camiones de basura, planeación de vuelos y rutas de trenes,...

  • Biología y Medicina: análisis de redes neuronales en el cerebro, interacción de proteínas, diseño de fármacos, estudio de la propagación de enfermedades,...

  • Química: representación de la estructura de moléculas y reacciones químicas.

  • Ingeniería Eléctrica: diseño y análisis de circuitos eléctricos y redes de comunicación.

  • Ciencias Sociales: estudio de la propagación de rumores, la influencia social y la formación de comunidades.

  • Deportes: análisis de estrategias de juego y relaciones entre equipos o jugadores.

La teoría de grafos sigue creciendo y resolviendo nuevos desafíos. ¿En qué área crees que podría aplicarse en el futuro? ¿Conoces más aplicaciones? ¿Te gustaría saber más sobre la teoría de grafos? Házmelo saber en los comentarios.


No hay comentarios:

Publicar un comentario