Vayamos de paseo

La primera entrada de esta sección corresponde a un problema del siglo XVIII y se sitúa en la ciudad de Königsberg (de Prusia Central en la antigüedad y que corresponde a la ciudad de Kaliningrado hoy en día que se encuentra en Rusia). En esta ciudad, el río Pregel (ahora llamado Pregolya) separaba la ciudad formando dos islas y había siete puentes que conectaban las distintas zonas de la ciudad de la manera siguiente:

Hasta ahora hemos situado el problema, pero, ¿qué problema había en esta ciudad? Pues bien, se cuenta que la gente de la ciudad se divertía de una forma muy peculiar “salir de una zona de la ciudad, ir paseando y tenían que pasar por todos los puentes una única vez y volver al lugar del que partían”. Bien, ningún ciudadano lo consiguió, ni lo conseguiría ahora ninguno (si no te lo crees inténtalo y/o sigue leyendo), la cuestión es: ¿Por qué?

La respuesta a este problema la dio Leonhard Euler en 1736 iniciando de esta manera con la teoría de grafos. Antes de seguir con la demostración de Euler, vamos a dar una sencilla explicación de lo que es un grafo. Un grafo viene dado por un conjunto de vértices (puntos) y de ejes (líneas) donde cada eje está unido a uno o dos vértices. Veamos algún ejemplo:

Una vez que sabemos lo que es un grafo, ¿qué relación tiene esto con el problema que tenían los ciudadanos de Königsberg? La clave principal está en que a partir del mapa de la ciudad con sus siete puentes, Euler dibujó un grafo en el que cada zona de la ciudad era un vértice y cada puente era un eje:

Para saber que no podemos pasar por todos los puentes (ejes) daremos un par de definiciones previas:

Grado de un vértice: el número de ejes incidentes con él, es decir, el número de ejes que tocan un cierto vértice. Por ejemplo, el vértice C tiene grado 3 y el vértice A grado 5.

Grafo conexo: un grafo en el que no hay vértices sueltos, sino que todos los vértices están unidos a al menos otro vértice.

Grafo Euleriano: grafo conexo en el que existe un camino (recorrido pasando por los ejes y los vértices) que contiene todos los ejes pero sólo una vez.

La última definición es la clave del problema, ya que si el grafo que corresponde a la ciudad de Königsberg no es Euleriano, entonces no podremos encontrar el camino deseado que buscaban los ciudadanos de aquella ciudad. Para ello utilizaremos el siguiente teorema:

Sea un grafo conexo con todos sus vértices de grado par o con dos vértices de grado impar. Entonces, el grafo es Euleriano.

Con este teorema vamos a ver que el grafo de la ciudad no es Euleriano. Para ello contemos el grado de cada vértice:

Vértice	Grado
A	5
B	3
C	3
D	3

Observamos entonces que todos los vértices tienen grado impar, con lo que tenemos que nuestro grafo de la ciudad de Königsberg no es Euleriano, luego no podemos encontrar un camino que pase únicamente una vez por cada puente y volvamos al sitio de partida. Así pues, menos mal que llegó Euler porque sino aún estaríamos paseando por los puentes sin encontrar el camino que queríamos.

He aquí un ejemplo de cómo las matemáticas han ayudado a resolver problemas reales de la gente. Además, es fácil demostrar que si en la ciudad hubieran tenido un puente más, sí que podrían haber hecho el recorrido que buscaban (ya tienes faena).

Si esto último te parece complicado, aquí te dejo otro ejercicio, ¿se puede dibujar el siguiente dibujo sin levantar el lápiz del papel y pasando sólo una vez por cada línea? (No hay que dibujarlo, sólo decir si se puede)

¡Nos vemos pronto!