El teorema de Grafos

Hoy os traigo,  por fin, la solución al problema del otro día. Sé que os habéis esforzado intentándolo, pero no pasa nada. Al fin y al cabo, he hecho un poco de trampa (el problema, aunque es sencillo, da pie a un desarrollo complejo). Veamos cómo se resuelve.

Lo que el problema pide es, en realidad, imposible. No se puede pasar por todos los puentes sin repetir alguno. Da igual por dónde empecéis, cuál sea vuestra ruta o el medio de transporte (a no ser que sea un barco, claro). Siempre llegaréis a una isla sin haber acabado el recorrido y habiendo pasado por todos los puentes disponibles desde esa posición. ¿Por qué? Observad la simplificación del problema:

Como veis, el problema queda reducido a estos cuatro puntos unidos por líneas (aristas). Esto es lo que se conoce como grafo. Introduzco ahora un concepto nuevo: el grado de los vértices. Es el número de aristas que inciden en cada punto. Así, tenemos un vértice de grado 3, uno de grado 5 y otros dos de grado 3. De esta forma, todos los vértices tienen grado impar. Entonces, ¿se puede llevar a cabo lo que pide el problema?

Imaginad un triángulo. Todos sus vértices son de grado par (en cada punto o nudo inciden dos aristas). Esto implica que puedes "salir" y "entrar" una vez en cada punto. O al revés. Entonces, se deduce que es posible recorrer todas las aristas de un triángulo una sola vez, volviendo al vértice del que se partió. Es lo que se conoce como ciclo euleriano. Esto se aplica a cualquier grafo cuyos vértices sean de grado par. Pero, ¿y si hay vértices de grado impar? Ya habréis deducido que, si el número de vértices de grado impar es impar, recorrer todo el grafo es imposible. ¿Y si este número es par? Os digo que tampoco. Y esto es un axioma, por lo que su demostración es bastante difícil. Solo hay una excepción a este enunciado.

La excepción es que haya solo dos vértices de grado impar en todo el grafo. Así, se produciría un camino Euleriano, en el cual se recorren todos los puntos siempre que se parta de uno de los nudos de grado impar. Además, siempre se termina en el otro vértice de grado impar. Probadlo en la imagen de arriba.

Por todo esto, se llega a la conclusión de que el problema del otro día, conocido como "el problema de los puentes de Könisberg", es imposible. La resolución de este problema, planteado por Leonhard Euler en el año 1736, se considera el primer artículo sobre la teoría de grafos y la topología: dos importantes ramas de la matemática. Esta ha sido, además, mi pequeña introducción al teorema de grafos, explicando de la forma más sencilla posible el concepto de grado.

Espero que os haya gustado. Un saludo, y hasta otra.