La firma del Diablo y los puentes de Königsberg. (Rogelio Fernández-Alonso)

 

En este caso estamos hablando de un problema de una rama de las matemáticas que se llama Teoría de las Gráficas (o de los Grafos). Un grafo es simplemente un conjunto de puntos (llamados vértices)

Recuerdo que cuando era niño algún compañero me puso el reto de trazar una figura sencilla: un cuadrado con sus dos diagonales. Pero el trazo debía hacerse “sin despegar el lápiz”. Ante la imposibilidad de resolver este torito, la figura era conocida como “la firma del Diablo”. En efecto, para trazar la firma del Diablo no se necesita ninguna habilidad especial; simplemente es imposible. Paradójicamente, a veces las matemáticas “resuelven un problema” llegando a la certeza de la imposibilidad para resolverlo. Tal es el caso de problemas como la cuadratura del círculo, la trisección del ángulo, la duplicación del cubo, el Teorema de Fermat y muchos otros.

En este caso estamos hablando de un problema de una rama de las matemáticas que se llama Teoría de las Gráficas (o de los Grafos). Un grafo es simplemente un conjunto de puntos (llamados vértices) conectados por líneas (llamadas aristas). Se dice que el gran matemático suizo Leonhard Euler concibió este tipo de objetos a raíz de un problema que se planteó en la ciudad de Königsberg (hoy localizada en Rusia), por la que cruza el río Pregel formando dos grandes islas. Siete puentes cruzan el río uniendo distintas porciones de tierra. Euler planteó el problema de hacer un paseo por los siete puentes en el cual ningún puente fuera cruzado más de una vez. A este tipo de paseos en un grafo se les llama ahora “eulerianos”. Consideremos la siguiente definición: el grado de un vértice es el número de aristas que pasan por él. A partir de los puentes de Königsberg, Euler enunció el siguienpe teorema: Un grafo admite un paseo euleriano, si y sólo si todos sus vértices tienen grado par o bien sólo dos vértices tienen grado impar. La demostración es muy sencilla. Si un grafo tiene un paseo euleriano hay un vértice de salida y uno de llegada. En el resto de los vértices por cada arista que llegue hay una que sale. Por tanto el grado de estos vértices es par. Si los vértices de salida y llegada del paseo son distintos, cada uno tendrá grado impar; si es el mismo vértice entonces tiene grado par. Inversamente, si el grafo cumple las condiciones descritas para los grados de los vértices se puede encontrar un paseo euleriano.

Regresemos a los puentes de Königsberg. Observemos que a cada porción de tierra llega un número impar de puentes. Abstrayendo la configuración de los puentes a un grafo obtenemos uno con 4 vértices (representando las porciones de tierra) unidos por 7 aristas (representando los puentes), en donde cada vértice tiene grado impar (tres de grado 3 y uno de grado 5). En la firma del Diablo los cuatro vértices tienen grado 3. Por eso en ambos casos tenemos la certeza de que es imposible realizar un paseo euleriano.

Rogelio Fernández-Alonso - Contenidos EMET