4. Unir mediante una línea

4.1. Puntos y líneas

Königsberg, 1736. ¿Es posible atravesar la ciudad cruzando cada uno de sus siete puentes una vez y sólo una vez?

Para solucionar este problema, Euler extrae la información esencial: la ciudad está dividida en cuatro zonas representadas por cuatro puntos, conectados mediante siete líneas que simbolizan los siete puentes.

El problema se transforma entonces en el siguiente: en este esquema, ¿existe un camino que pase sólo una vez por cada línea? Es el inicio de la teoría de los grafos. La respuesta de Euler fue: depende de cuántos puntos existan en los que concurren un número impar de líneas.

Sólo existe solución si dicho número es igual a cero o dos.

• Leonhard Euler (1707-1783)

4.2. ¡Cuatro colores bastan!

¿Cuántos colores necesitamos para colorear un mapa, de manera que dos países adyacentes tengan colores distintos?

La teoría de grafos nos permite representar este problema y reducir el número de casos por estudiar. Gracias a los ordenadores, se ha podido analizar un gran número de situaciones.

La teoría de grafos se utiliza para representar y estudiar situaciones muy concretas como redes de telecomunicaciones, circuitos electrónicos, redes de distribución -agua, gas, electricidad, correos...- y muchos otros problemas de logística, transporte y producción.

4.3. ¿Dígame?

En una red de comunicaciones locales ¿cómo se realizan tus llamadas telefónicas?

Viajan de repetidor en repetidor hasta la central más cercana a tu interlocutor que será avisado por un tono.

En una ciudad, estas centrales de la red telefónica están ubicadas de la mejor manera posible teniendo en cuenta la distribución irregular de las calles.

Cada central tiene asignada una zona de proximidad de la llamada en forma de polígono conectado con los demás vecinos.

Estas zonas forman una teselación de la ciudad, denominada mosaico de Voronoï. Si se conectan las centrales de zonas vecinas, se obtiene un grafo que representa los cables por los que viaja la llamada.

Los grafos, la teoría de la probabilidad y la geometría se unen para permitir la comunicación en condiciones óptimas.