Juegos para colorear grafos

Abstract

En este trabajo se presentan aplicaciones informáticas de carácter lúdico y didáctico, que tienen como objetivo la comprensión de las estrategias para colorear grafos. La primera de ellas es un juego de dos jugadores (uno de ellos puede ser el ordenador) en el que, alternativamente, cada jugador colorea un vértice de un grafo previamente construido. Los colores se eligen de una lista adecuada para cada grafo. Vence el primer jugador si consigue que, en algún momento, el segundo jugador no disponga de ningún color válido para seguir coloreando el grafo. Si, por el contrario, el grafo se colorea correctamente, el vencedor es el segundo jugador. La segunda aplicación es también un juego decoloración de grafos, pero en esta ocasión se colorean las aristas. Ambas aplicaciones disponen de un banco de grafos del que se elige uno en cada nuevo juego.