La historia de la teoría de grafos comienza en 1736, cuando Leonhard Euler, en su artículo [1] escrito en latín, resolvió el denominado problema de los puentes de Königsberg. En esa época, Königsberg era una ciudad de Prusia Oriental, luego fue alemana, y desde 1945 se denomina Kaliningrado y pertenece a Rusia; está en el enclave ruso del mismo nombre, junto al mar Báltico, que, con quince mil kilómetros cuadrados y medio millón de habitantes, tiene frontera con Lituania (al este) y con Polonia (al sur). De camino hacia su desembocadura en el Báltico, Königsberg estaba atravesada por el río Pregel, que actualmente se conoce como Pregolia.

Al atravesar Königsberg, el río Pregel se bifurcaba y formaba una isla en el interior de la ciudad (y otra que se extendía hacia fuera), de manera que la ciudad quedaba dividida en 4 regiones distintas, que estaban unidas por 7 puentes, tal como se muestra en la figura.

Por si el lector siente curiosidad por la situación actual de los puentes, de los siete de la época de Euler, uno fue reconstruido, en el mismo lugar, en 1935, y dos de los puentes quedaron destruidos en la Segunda Guerra Mundial; más tarde, dos más fueron demolidos y sustituidos por carreteras modernas. Y, por supuesto, la ciudad ha crecido y se han añadido puentes nuevos, así que la configuración actual ya no es la misma, pero eso no tiene relevancia en lo que aquí perseguimos, así que volvamos a la época de Euler.

Entre los intelectuales de la ciudad, se había popularizado el siguiente problema:

En la ciudad de Königsberg, dividida por el río Pregel en cuatro regiones distintas unidas a través de siete puentes, ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo sólo una vez cada uno, y regresando al mismo punto de partida?

Eso no parecía un problema matemático, pues las matemáticas tradicionales no tenían ninguna utilidad para abordarlo. Ni la geometría, ni la aritmética ni el cálculo diferencial tenían ahí nada que decir. No había medidas, ni números. Si se encuentra un recorrido que cumple los requisitos, el problema ya está resuelto. Pero, si no lo encontramos, ¿cómo saber si no hemos buscado suficientemente bien o si ese camino no puede existir? ¿Qué se podía hacer, aparte de emplear fuerza bruta e intentar probar con todos los caminos posibles?

Para resolver el problema, Euler recurre a una abstracción del mapa y tiene en cuenta, exclusivamente, las regiones terrestres y las conexiones entre ellas. Cada región queda representada con un punto, y cada puente mediante una línea que une dos puntos, tal como muestra la figura. De este modo, el problema se reduce a saber si existe o no un camino que comience por uno de los puntos, recorra todas las líneas una sola vez y regrese al mismo punto de partida.

Con esa formulación, resolver el problema le resultó, ya, muy sencillo. Si existiera un recorrido tal como el que se propone, incluso sin exigir que el punto inicial y final sean el mismo, los puntos intermedios necesariamente han de estar conectados a un número par de líneas (si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente). Esto significa que tanto el punto inicial como el final son los únicos que podrían estar conectados con un número impar de líneas (si el recorrido debe comenzar y acabar en el mismo punto, ese punto tampoco puede tener un número impar de líneas). Pero hay cuatro puntos en los que inciden un número impar de líneas, así que tal recorrido no puede existir.

El esquema que ideó Euler para resolver el problema de Königsberg da lugar a lo que se denomina un grafo; en un grafo, los puntos se denominan vértices y las líneas se denominan aristas. Además, y aunque aquí no lo detallaremos, Euler resolvió el problema de manera mucho más general a como estaba planteado originalmente, demostrando que las consideraciones anteriores sobre el número par o impar de aristas en los vértices dan lugar a una condición necesaria y suficiente para que, en un grafo cualquiera, exista un recorrido de ese tipo. No está de más comentar que las demostraciones de Euler no tenían el rigor de las matemáticas actuales, y hay quien considera que realmente no dio una demostración completa de la suficiencia; en cualquier caso, Carl Hierholzer resolvió definitivamente la cuestión con una demostración algorítmica (publicada póstumamente en 1873, más de cien años después del trabajo de Euler).

La abstracción de Euler supuso el nacimiento de una nueva rama de las matemáticas, la teoría de grafos (incluso, podríamos decir, el nacimiento de la topología). Si bien la naturaleza está regida mediante ecuaciones diferenciales o en derivadas parciales (casi todas las ecuaciones importantes de la física lo son), estas herramientas no tienen, aquí, ninguna utilidad. Las ecuaciones en derivadas parciales se ocupan de problemas continuos, en los que aparecen los números reales o los complejos, pero ahora nos encontramos con problemas discretos. Los problemas continuos están presentes por doquier en física o en ingeniería (por supuesto, también en otras ciencias, que los han incorporado más recientemente), pero en informática son mucho más importantes los problemas discretos (internet es un grafo enorme, por ejemplo). De ahí el auge actual de la matemática discreta, pese a que no se incluye en los planes de estudio de las titulaciones científicas, salvo en matemáticas o en informática (véase, por ejemplo, [3]). Lo mismo ocurre, por cierto, con la teoría de números y su uso en criptografía, omnipresente en la seguridad y las comunicaciones informáticas.

Hay muchas propiedades que se pueden estudiar en los grafos, pero no es éste lugar para explicarlas. En vez de eso, y para ver la utilidad de la teoría de grafos, vamos a ver un par de problemas que se pueden analizar mediante teoría de grafos; más en concreto, mediante coloraciones de grafos. Para ello, sólo vamos a necesitar decir que colorear un grafo mediante \(k\) colores distintos significa asignar, a cada uno de los vértices, uno de los \(k\) colores disponibles, de manera que no haya dos vértices adyacentes (es decir, unidos por una arista) que tengan el mismo color. Aunque no es lo que ahora nos preocupa, no está de más comentar que un problema interesante es, dado un grafo, encontrar el menor número de colores con el que es posible colorearlo (el llamado número cromático del grafo). Tanto en estos problemas, como en otros de la teoría de grafos, existen algoritmos, pero no siempre son suficientemente rápidos, sobre todo cuando el grafo es grande. Esto hace que la teoría de grafos sea un área de investigación muy activa.

Confección de horarios

Uno de los usos del coloreado de grafos es la elaboración de horarios. Si hay dos actividades que no se pueden simultanear (bien porque hay una persona que tiene que estar en las dos actividades, o porque no hay recursos suficientes para que ambas tengan lugar a la vez), esas dos actividades serán, en un grafo, dos vértices conectados por una arista, y elaborar un horario equivaldrá a colorear un grafo. Vamos a verlo con un ejemplo sencillo, que realmente se podría resolver por tanteo. A todos se nos pueden ocurrir ejemplos de elaboración de horarios mucho más sofisticados que el que aquí presentamos (es decir, grafos con muchos más vértices y aristas), de modo que automatizarlo con herramientas informáticas destinadas a ello facilita enormemente el trabajo.

Supongamos que, en la sesión inaugural de un festival de cine, se proyectan diez películas. Cinco famosos críticos cinematográficos, de nombres Ana, Benito, Carlos, Daniel y Eva, han decidido ir a algunas de las películas, tal y como se muestra en la siguiente tabla:

Los organizadores del festival disponen de suficientes salas de proyección, así que puede haber tantas sesiones simultáneas como se desee (en cada sesión sólo se proyecta una película), pero cada película la quieren proyectar una sola vez, y prefieren usar el menor número de franjas horarias posible. Además, han decidido que todos los críticos puedan acudir a las películas que quieren ver. ¿Cuántas franjas horarias de proyección son necesarias?

Para plantear esto como un problema de coloración de grafos, construyamos un grafo en el que los vértices son las películas, y las aristas unen dos películas si un mismo crítico quiere verlas. Por ejemplo, los vértices 1 y 2 están unidos por una arista pues Ana quiere ver ambas películas (también Benito, pero lo mismo da un crítico interesado en ver la película que más de uno). Los vértices 1 y 8 no están unidos porque ningún crítico tiene intención de asistir a las proyecciones de ambas películas. Esto da lugar al grafo de la izquierda en la figura adjunta.

Podemos suponer que cada franja horaria es un color, y dos películas conectadas por alguna arista no pueden compartir franja horaria de proyección; es decir, tienen que ser vértices de distinto color. Así que lo que tenemos que hacer es colorear el grafo con el menor número posible de colores.

La teoría de coloraciones de grafos (que aquí no vamos a explicar) nos asegura que es imposible conseguirlo con menos de cinco colores. Con cinco colores sí se puede, tal como se ve en la parte derecha de la figura (la solución no es única). Así, la organización ha de reservar cinco franjas horarias: la primera para las películas 1 y 9 (se proyectan a la vez en salas distintas), la segunda para las películas 2 y 6, la tercera para las películas 3 y 7, la cuarta para las películas 4 y 8, y la quinta para las películas 5 y 10.

Resolver un sudoku es colorear un grafo

Un sudoku habitual, de tamaño \(9 \times 9\), es una cuadrícula con \(9\) filas, \(9\) columnas y \(9\) bloques de tamaño \(3\times3\), como en la figura.

Resolver un sudoku es rellenarlo con números del \(1\) al \(9\) con un número en cada casilla, de forma que cada fila, cada columna y cada bloque contenga los números \(\{1, 2,\dots, 9\}\) exactamente una vez (cuando se emplea como pasatiempo, que es lo habitual, el sudoku comienza con algunas casillas ya rellenadas, y el objetivo es rellenar el resto, pero eso no es relevante ahora).

¿Qué tiene que ver un sudoku con la teoría de grafos? Para ver la relación, construimos un grafo de la siguiente forma:

1. Cada casilla va a ser un vértice del grafo, con lo cual el grafo tendrá \(9^2 = 81\) vértices.
2. Dos vértices estarán unidos por una arista si no pueden tener el mismo número, es decir, si las correspondientes casillas están en la misma fila, en la misma columna o en el mismo bloque \(3\times3\). No es complicado ver que, de esa forma, el grafo tiene \(810\) aristas: a cada vértice le corresponden \(8\) aristas de su bloque \(3\times3\), \(6\) más de de su fila, y \(6\) más de su columna, luego de cada vértice salen \(20\) aristas; eso da un total de \(81 \cdot 20/2 = 810\) aristas (se divide por \(2\) pues cada arista la habíamos contado dos veces, una por cada uno de los dos vértices que une). 

Resolver un sudoku es rellenarlo usando \(9\) números; pero daría igual usar \(9\) números o \(9\) colores. Así pues, resolver un sudoku es exactamente lo mismo que encontrar una coloración del grafo usando \(9\) colores. De este modo, los sudokus y su solución han quedado modelizados por medio de la teoría de grafos, y podríamos utilizar los algoritmos de la teoría de grafos para resolver sudokus, con varias casillas previamente rellenadas; un ordenador con un programa adecuado lo podría hacer de manera prácticamente instantánea. Por supuesto, no es eso lo que se pretende, ya que resolver un sudoku es un desafío mental y la idea es resolverlo pensando. Pero sí que puede ser útil para construir sudokus. Desde luego, esto se puede aplicar no sólo a sudokus \(9 \times 9\), sino de cualquier otro tamaño; se pueden construir sudokus de tamaño \(n^2 \times n^2\) para cualquier entero \(n \ge 2\): tendrán \(n^2\) filas, \(n^2\) columnas y \(n^2\) bloques de tamaño \(n \times n\), y hay que rellenarlos usando los números desde \(1\) hasta \(n^2\), lo cual equivale a colorear el correspondiente grafo con \(n^2\) colores.

Para finalizar, y como curiosidad, comentemos que el número de formas distintas de rellenar un sudoku \(9 \times 9\) (es decir, el número de sudokus distintos que se pueden construir) es enorme, y no es fácil de calcular. Dicho número es
\(6\,670\,903\,752\,021\,072\,936\,960 \approx 6.671 \cdot 10^{21}\), véase [4] o [2]. Asimismo, hay \(288\) sudokus distintos de tamaño \(4 \times 4\); pero, para sudokus de tamaño \(16 \times 16\), su número no se conoce.

Referencias

[1] L. Euler, Solutio problematis ad geometriam situs pertinensis, Commentarii Academiae Scientarum Imperialis Petropolitanae 8 (1736), 128–140. Reimpreso en Opera Omnia Series Prima, Vol. 7, pp. 1–10, 1766.

[2] B. Felgenhauer y F. Jarvis, Mathematics of Sudoku I, Mathematical Spectrum 39 (2006/2007), no. 1, 15–22.

[3] J. M. Gutiérrez Jiménez y V. Lanchares Barrasa, Elementos de matemática discreta, Servicio de Publicaciones de la Universidad de La Rioja, 2010.

[4] K. Y. Lin, Number of Sudokus, Journal of Recreational Mathematics 33 (2004), no. 2, 120–124.