En esta ocasión publicaré la solución al juego anterior http://www.ellibrepensador.com/2010/12/12/un-juego-de-logica-para-todos/, que algunas personas acertasteis (tanto aquí como en Facebook); explicaré de forma breve la teoría que subyace a este juego y, finalmente, propondré otro para aquéllos que deseen pasar un rato pensando ‘un poquito’.
Como averiguasteis casi todos, sí es posible trazar un camino que parta de un punto cualquiera y retorne a él, pasando por todos los demás puntos, y una sola vez por cada una de sus líneas. Por ejemplo, el camino a-b-d-e-f-b-i-f-j-g-b-c-g-k-j-i-h-d-a es uno entre tantos posibles que pasa por todos los puntos y aristas, estas últimas sólo una vez.
La figura propuesta se estudia en Matemáticas y recibe el nombre de grafo. Un grafo G está compuesto por un conjunto de vértices V= {v1, v2, .., vn} y aristas E = {e1, e2, .., en}, y se representa como G = (V,E) al grafo de V vértices y E aristas. En nuestra figura, los vértices serían todos los puntos a, b, c, etcétera y las aristas serían todas y cada una de las líneas que unen estos vértices, como la ab o la bd, por ejemplo. Las aristas pueden ser unidireccionales o bidireccionales, lo que daría como resultado un grafo dirigido y un grafo no dirigido, respectivamente.
Las propiedades de los grafos son muchas y su complejidad poco nos interesa a efectos prácticos. Sin embargo, de todas las propiedades, a la vista del juego propuesto, sí valdría la pena destacar escuetamente varios conceptos:
– Un recorrido entre dos vértices v1, v2 es un camino que une ambos vértices, con la particularidad de que pueden repetirse vértices entre ellos, pero no aristas. En nuestra figura, un recorrido podría ser a-b-d-e, que une a con e sin repetir arista y pasando por b y d.
– Un circuito para un vértice v1 es un camino que parte de él y llega a sí mismo, con la particularidad de que pueden repetirse vértices pero no aristas. En nuestra figura, un circuito podría ser a-b-d-a, que vuelve a a sin repetir arista y pasando por b y d.
Hay una clase especial de recorridos y circuitos: los denominados circuitos y recorridos eulerianos (en honor a Leonhard Euler, el prolífico matemático suizo). Un recorrido euleriano es aquel recorrido que une dos vértices v1, v2 de un grafo pasando por todos los vértices y aristas sin repetir estas últimas; un circuito euleriano es un circuito que parte de v1 y llega a v1, pasando por todos vértices y aristas sin repetir éstas últimas. Nótese que no se especifica nada acerca de repetir vértices.
Lo que acabáis de resolver en este juego es un circuito euleriano.
Sin embargo, para una futura ocasión, os sería de gran ayuda conocer una importante propiedad de los grafos. Ésta dice que un grafo G sólo puede contener un circuito euleriano si y solo si el número de aristas que converge en todos y cada uno de los vértices es par (vértices de grado par). Si observáis el diagrama del juego, observaréis que esta propiedad se cumple, por lo que se podría haber respondido ‘sí’ sin necesidad de hallar uno de esos circuitos, aunque se agradece que se aporte una prueba -por norma general. Tanto es esto así, que basta con que quitéis una sola arista al diagrama o añadáis una más para que el ejercicio sea literalmente imposible.
Sin embargo, si quitáis o añadís una arista, por lógica hay dos vértices que pasarían a tener un número de aristas convergentes impar. Cuando esto sucede, se cumple la propiedad de que un grafo G sólo puede contener un recorrido euleriano si y solo si hay dos vértices de grado impar (sólo dos). Os animo a probar el ejercicio de ambas maneras.
Esto que puede parecer absurdo o trivial, no lo es en absoluto. Mediante el método de grafos, Euler consiguió resolver el famoso enigma de los puentes de Königsberg http://es.wikipedia.org/wiki/Problema_de_los_puentes_de_K%C3%B6nigsberg siendo ése mismo el momento en el que comenzó a desarrollarse lo que se conoce como Teoría de Grafos, una rama de la Matemática Discreta con innumerables y potentes aplicaciones en la actualidad, desde la informática o las telecomunicaciones a los sistemas de optimizado, carreteras o rutas, debido a las propiedades algebraicas de dichos cuerpos.
(Bibliografía: “Matemáticas discreta y combinatoria”, Ralph Grimaldi)
**
Termino esto cumpliendo mi promesa: allá va otro juego de lógica. Dice así:
“Si construyésemos una nueva Torre Eiffel que fuese el doble de la actual, guardando las proporciones, ¿cuánto pesaría?”.
Para quien sepa la solución, esta vez, sí le animo a que nos explique a los demás su razonamiento.
Ánimo, y saludos.
