jueves, 24 de julio de 2008

Qué problemas se podrían solucionar usando grafos

La teoría de grafos es una de las herramientas que aparece más frecuentemente en el análisis matemático de los juegos.
Nació con los puentes de Königsberg, se encuentra en el juego de Hamilton, da la estrategia adecuada para los acertijos de cruces de ríos, como el del pastor, la oveja, la col y el lobo, el de los maridos celosos, y resuelve también muchos otros más modernos como el de los cuatro cubos de la Locura Instantánea...
Un pastor, con una col, una oveja y un lobo (se supone que hasta cierto punto amaestrado) se encuentra a la orilla de un río que quiere atravesar. Hay en su orilla una barca en la que cabe él y una sola de sus pertenencias al tiempo. ¿Cómo se las ingeniará para pasarlas todas? Si deja solas a un lado oveja y col, ésta será liquidada rápidamente por la oveja. Si deja oveja y lobo solos a un lado, el lobo se zampará a la oveja. En cambio al lobo no le atrae nada la col y bien se puede quedar solo con ella. El problema es clásico y fácil de resolver sin grandes esfuerzos sistemáticos. Pero existe una solución sencilla acudiendo, como sucede en muchas ocasiones en que se trata de realizar secuencialmente un conjunto de tareas, a la teoría de grafos. Ver más en:
El problema de locura instantánea, parte de que se tienen 4 cubos y cada una de las caras del cubo esta pintada por un color diferente (ejemplo: amarillo, morado, rosado, fucsia). El problema consiste en apilar los cubos uno sobre el otro, de modo que uno vea los 4 colores, desde el frente, por detrás, por la izquierda por la derecha. Como existen 331,776 formas diferentes de apilar los cubos, lo mejor es utilizar un método que no implique probar con todas las posibilidades. Mediante los grafos se puede encontrar solución a este problema.
Una explicación de este último problema y algunas variaciones del mismo, es lo que se denomina EL PUZZLE DE LOS CUATRO COLORES y esta bien descrito en:
Existen más problemas que pueden ser encontrados en libros de teoría de juegos o incluso en los de Matemáticas discretas, solo queda que seleccione su proyecto y lo implemente como trabajo final.