Leonhard Euler demostró la imposibilidad de recorrer los siete puentes con un paseo continuo sin volver a recorrer dos veces el mismo puente (1736). La resolución del problema le dio fama y supuso el nacimiento de la teoría de grafos. El auge de esta teoría se debe a que transforma problemas de la vida real en problemas abstractos utilizando líneas y puntos.

Un grafo es un conjunto de vértices y aristas o arcos. Una sucesión de puntos (no necesariamente distintos) es un sendero o camino. Su longitud es el número de aristas que tiene.

Teorema de Euler: un grafo plano y conexo verifica que V – A + R = 2, donde: V es el número de vértices; A, el número de aristas o arcos; y R, el de regiones que delimita (siendo una de ellas la región infinita).

¿Existe alguna forma de pasear por la ciudad cruzando una sola vez todos los puentes y regresando al origen?

Para recorrer una sola vez cada arista del grafo, del vértice de salida debe partir una sola arista, o si se vuelve, también se sale de nuevo (cada vez que se pasa por el vértice se suman dos aristas), siendo par + 1 = impar.

Los vértices intermedios deben tener un número par de aristas (una de entrada y otra de salida). Si es así, y el inicio es distinto al fin, tenemos un camino euleriano.

Si se parte del punto en que finaliza, tenemos en ese punto también un número par de aristas: ciclo euleriano (geoconexo con todos los vértices pares).

Existe un sendero cíclico S que pasa por todos los vértices y que recorre una sola vez todos los arcos de un grafo G si y solo si el grafo es conexo y todos los nudos son pares (teorema de Euler).

En 1859, William Rowan Hamilton planteó un juego en el que hay que recorrer todos los vértices de un dodecaedro sin repetir los vértices y volviendo al punto de partida.

Se aplica a la optimización de rutas. Se puede resolver en términos de distancia o de coste.

Gustav Kirkhoff, utilizando la Ley de Ohm, lo aplicó a problemas de redes eléctricas (grafo no dirigido, conexo y sin ciclos).

¿Cómo podemos colorear un mapa con el mínimo número de colores, iluminando países limítrofes de distinto color?

Se resolvió gracias a los ordenadores en 1976 (Kenneth Appel y Wolfgang Haken): problema de los cuatro colores.

Si un grafo es euleriano, el mapa de las caras es bicoloreable.

Aplicaciones de la teoría de grafos:

• Optimización de recursos.
• Ruta óptima: asfaltado de calles, recogida de basuras, reparto de cartas, rutas de navegadores…
• Algoritmos: investigación operativa, computadoras, robótica…
• Traductores de idiomas.
• Sociología.
• Orientar tráfico urbano.
• Gestión de proyectos (PERT).

Principales fuentes consultadas:

• Cristina Jordan Lluch: curso Teoría básica de grafos y análisis de 4 problemas conocidos, de la Universidad Politécnica de Valencia.