Introducción
Esta actividad pertenece al libro de GeoGebra Redes y Grafos.
¿Qué es una red?
Piensa en las personas que conoces y te conocen, con las que hablas a menudo. Con cada una de ellas tienes una conexión, algo que no pasa con las demás personas. Pero, a su vez, cada una de esas personas, no solo te conoce a ti, conoce a otras, ya sean conocidas tuyas o no.
A medida que empieces a expandir esta cadena de conocidos, surgirán más y más personas que tú no conoces directamente, pero con las que podrías comunicarte si supieses cuáles son las personas intermedias que te separan de ellas.
Entre todas esas personas hay entonces una gran cantidad de conexiones, la gran mayoría de ellas desconocidas para ti. Decimos que el conjunto de todas esas personas y sus conexiones forman una red (en este caso, una red social).
Si cambiamos las personas por ciudades y los reconocimientos por carreteras, obtenemos una red de carreteras. Si hablamos de teléfonos fijos y cables telefónicos obtenemos una red telefónica. Hay montones de cosas, personas, instituciones, hechos, símbolos, etc. que pueden interconectarse de diferentes modos. Cada uno de esos conjuntos de conexiones forma una red.
¿Qué es un grafo?
Un grafo es un conjunto de puntos (vértices o nodos) y líneas que los conectan (aristas o arcos). El grado de un vértice es el número de aristas que concurren en él.
Los grafos expresan las conexiones existentes en una red. Con el paso de los años, la Teoría de Grafos ha ido generando tantas aplicaciones que hoy se usa prácticamente en el análisis de cualquier red.
¿Cuándo y cómo aparecen los grafos?
Comparativamente con otras áreas matemáticas, los grafos son bastante recientes. Surgen a partir de una curiosa pregunta planteada a principios del siglo XVIII en la ciudad rusa de Kaliningrado (entonces llamada Königsberg). El problema de los puentes de Königsberg se preguntaba si sería posible realizar un paseo andando sin salir de la ciudad, dividida en cuatro regiones por el río Pregolia, de modo que se recorriese una sola vez cada uno de los siete puentes que las conectaban.
Este problema llama la atención del genial matemático Leonhard Euler, que estaba de visita en la ciudad, quien demuestra en 1736 que tal paseo es imposible de realizar. Esta demostración está considerada la cuna de la Teoría de Grafos. En ella, Euler conjuga tres grandes técnicas demostrativas.
Primero, sintetiza al máximo la situación, reduciendo cada una de las cuatro regiones del mapa de la ciudad a un punto y cada uno de los siete puentes a una línea, obteniendo lo que hoy se conoce como grafo dual del mapa, consistente en cuatro puntos unidos por siete líneas, como muestra la figura. De este modo, el problema original equivale a dibujar este grafo con un solo trazo, sin levantar el lápiz y recorriendo cada línea una sola vez.
Segundo, Euler emplea un antiguo pero potentísimo método de demostración llamado reducción al absurdo. Euler sabe que habrá demostrado la imposibilidad del paseo si, razonando a partir de la suposición de que tal paseo existiera, alcanza una contradicción flagrante, un absurdo.
Finalmente, para alcanzar esa contradicción, Euler aplica un criterio de paridad. El grafo tiene cuatro vértices. Como solo puede haber un vértice de salida y uno de llegada, los otros vértices tienen que ser vértices de tránsito, es decir, ni se empieza ni se acaba en ellos. Pero eso es imposible, ya que todo vértice de tránsito tendría que tener un número PAR de aristas (la mitad de ellas para llegar al vértice y la otra mitad para salir de él), y todos los vértices del grafo tienen grado impar (3 o 5). Así que… ¡el paseo buscado no puede existir! Los ciudadanos de Königsberg que lo intentaran estaban condenados de antemano al fracaso, como puedes comprobar en la siguiente actividad.