La partícula grafo (del griego “graphe”, que significa escribir) forma parte de muchos términos relacionados con la escritura, es decir, con el sistema de signos utilizado para representar ideas o palabras, unas palabras construidas a su vez combinando esos signos básicos de cada idioma que constituyen las letras. Pero además, grafo es una palabra en sí misma, con un significado propio: los lingüistas la emplean para denominar el modo de escribir cada letra, a base de combinar líneas y puntos.

No es de extrañar entonces que cuando los matemáticos hemos tenido que ponerle nombre a los diagramas de líneas y puntos, con los que se representan por ejemplo las vías de comunicación y los lugares que conectan esas vías (respectivamente), hayamos acudido también a la palabra grafo. La Teoría de Grafos es una rama de las Matemáticas que se dedica a resolver los problemas que plantean encontrar caminos que recorran las líneas (aristas) pasando por los puntos (vértices), cumpliendo determinadas condiciones.

El origen de esta Teoría se remonta al siglo XVIII, con el problema de los puentes de Köninsberg. En esta ciudad, que tras formar parte de Prusia y de Alemania pasó a formar parte de Rusia y actualmente se denomina Kaliningrado, existían siete puentes que unían las cuatro zonas en las que el terreno quedaba dividido por el río Pregel, y sus habitantes se plantearon encontrar un camino que recorriera una sola vez cada uno de los puentes y terminara regresando a la zona de inicio.

La solución la alcanzó en 1763 el gran matemático suizo Leonhard Euler (1707-1783). Para ello, representó el mapa de la ciudad de modo simplificado, donde cada zona es un punto/vértice y cada puente una línea/arista, obteniendo así un grafo en el que el número de aristas que concurren en cada vértice (lo que de define como grado del vértice) resulta ser siempre impar (3 ó 5). Como para iniciar y terminar el recorrido en un mismo vértice, lo mismo que para pasar por él, se necesitaría que ese vértice tuviera un número par de aristas (una para salir en el comienzo, otra para volver al finalizar, y una pareja de aristas para entrar y salir si se va de paso por ese punto), y ninguno de los vértices de nuestro grafo lo tiene, el problema no tiene solución.

Euler generalizó este resultado, resolviendo los que desde entonces se denominan problemas eulerianos: se trata de los típicos retos que se plantean en esos pasatiempos dónde se pide realizar dibujos de un sólo trazo (sin levantar el lápiz del papel), que en definitiva nos enfrentan a situaciones en las que hay que encontrar un camino que se inicie y termine en un mismo vértice, recorriendo todas las aristas del grafo sin repetirlas. Para resolver la cuestión, Euler demostró el teorema que lleva su nombre, estableciendo que ese camino solución existe (en cuyo caso el grafo se denomina euleriano) si y solo si el grado de todos los vértices del grafo es par.

Si intercambiamos las condiciones impuestas sobre los vértices y aristas del camino, buscando ahora recorrer todos los vértices del grafo sin repetirlos, nos encontramos con los denominados problemas hamiltonianos. Su nombre recuerda al matemático irlandés William R. Hamilton (1805-1865), creador en 1857 del juego icosiano, en el que se plantea un típico problema de este tipo sobre un dodecaedro, poliedro formado por 12 pentágonos regulares, que presenta 30 aristas y 20 vértices, cifra esta última que en griego se dice “eikosi”, expresión que da lugar al adjetivo icosiano. El dodecaedro estaba construido en madera, y en cada uno de sus vértices se situaba un clavo representando una ciudad, denominada por su inicial (como curiosidad, Hamilton utilizó la X para “Xerés”, refiriéndose a Jerez), y el juego consistía en ir haciendo un camino con un cordel, que se iniciara en una ciudad/vértice, fuera pasando a través de las aristas por el resto de ciudades/vértices una sola vez, y finalizara regresando de nuevo al inicio.

En este caso el reto sí que tiene solución, pero su generalización sobre un mapa cualquiera de ciudades/vértices y carreteras/aristas, en el que se busca encontrar el camino más corto para realizar un viaje que pase por cada ciudad/vértice una sola vez y regrese al inicio, supone un problema para el que no existe un algoritmo general de solución. Es el denominado problema del viajante, cuya complejidad supone realizar en según qué ejemplos larguísimos cálculos, no existiendo algoritmos eficientes para resolverlo. Así es como lo que comenzó como un juego se ha convertido en un desafío pendiente, cuya solución supondría un gran avance de las Matemáticas, con múltiples aplicaciones que van desde la logística (para distribuir productos por nuestras ciudades reales) hasta la genética (donde los fragmentos de ADN a combinar sustituyen a las ciudades).