Grafos y aplicaciones


La teoría de grafos, es una parte de las Matemáticas que comenzaron en clave de juego y se han convertido en un instrumento fundamental de la Matemática Aplicada. Los problemas de transporte, la combinatoria poliédrica, los problemas de secuenciación de actividades usan de la Teoría de Grafos, para resolver muchos de los problemas de estas áreas.


Encontrar una condición necesaria y suficiente para que sea posible dibujar un grafo no dirigido, sin levantar el lápiz.

Un grafo es dibujable si es posible recorrerlo de manera que cada arco se recorre un sola vez. Está por tanto permitido pasar por un vértice varias veces. Un grafo que admite un recorrido de este tipo se dice que es euleriano, si el vértice de inicio y final es el mismo. En caso de que el recorrido no sea cerrado, pero se pueda pasar por cada arista sólo una vez, se dice que es semieuleriano.

Sugerencias.

Aquí tienes un explicación completa de la solución

Decimos que un grafo es hamiltoniano si admite un recorrido hamiltoniano. Un recorrido hamiltoniano es un camino cerrado, que pasa por cada uno de los vértices del grafo, una sola vez. Ahora, por tanto, está permito recorrer alguna arista más de una vez. Un grafo es conexo cuando es posible pasar de un vértice cualquiera a otro vértice cualquiera, por arcos del grafo. No se conoce ningún criterio que permita saber si un grafo conexo es o no hamiltoniano. Pero algunos grafos si que admiten demostraciones de que no son hamiltonianos. ¿Serías capaz de demostrar que este grafo no es hamiltoniano?

Este problema no es sencillo. Aquí tienes una demostración

(1) Aunque en teoría está permitido, esto no puede pasar

El siguiente grafo tiene un circuito hamiltoniano indicado por las líneas más oscuras. Existe sólamente otro circuito hamiltoniano ¿Serías capaz de encontrarlo?

Propuesto por Roger Penrose en La nueva mente del emperador (1989).

Ésta es la solución al problema, pero antes de mirarla, inténtalo tú

El juego del dominó es uno de los juegos más populares y de gran tradición en muchos pueblos de España. Se juega por parejas. Está compuesto de 28 fichas que se reparten entre cuatro jugadores (7 para cada uno). En el desarrollo del juego cada jugador pone una ficha (si puede, porque si no es así, entonces pasa al siguiente jugador), que coincida en puntuación con una cualquiera de las fichas de los dos extremos. Gana la partida, la pareja que consigue que uno de sus jugadores se quede sin fichas, en cuyo caso se apunta a la otra pareja la suma de los puntos de sus fichas, las que no ha podido poner. Pierde la pareja que antes llega a una puntuación previamente acordada. Uno de los problemas de combinatoria más antiguo con el dominó, pide determinar de cuántas formas pueden colocarse en hilera todas las fichas que tienen una puntuación menor o igual a n, siendo n un número entre 0 y 7. Por ejemplo, para n = 3, las ficha que hemos de colocar en serie serían:

Y una de las formas de colocarlas sería ..., bueno para este caso el problema es imposible. ¿Sabrías demostrarlo?.

Para n = 2, las fichas son

 

Y hay dos soluciones para ponerlas en serie, que en este caso difieren en el sentido del recorrido

Bueno, la cuestión es saber cuando es posible ponerlas en serie, y cuando no, según los valores de n. Este problema no es sencillo, pero con la teoría de grafos se puede resolver de manera elegante. Pincha aquí, para verla.