Livre Graphes et Algorithmes – Jeux grandeur nature.
Règles du jeu et exemple.
Graphe. Le jeu se déroule avec un graphe quelconque. Considérons par exemple le graphe suivant composé de cinq sommets.
Nombre de joueurs. Le nombre de joueurs est égal au nombre de sommets dans le graphe. Le jeu est collaboratif : tous les joueurs gagnent ou tous les joueurs perdent. Dans notre exemple, il y a cinq joueurs.
Accessoires. Chaque joueur a une chasuble de couleur. Les couleurs des chasubles sont fixées à l’avance. Pour les cinq joueurs précédents, nous pouvons avoir par exemple deux joueurs avec une chasuble rouge, deux joueurs avec une chasuble bleue et un joueur avec une chasuble verte.
But du jeu. Les joueurs doivent se positionner sur les sommets du graphe (un joueur par sommet) de telle sorte que, pour chacune des arêtes du graphe, les deux joueurs aux deux extrémités de l’arête aient des chasubles de couleur différente.
Exemple de solution. La figure suivante décrit une solution pour notre exemple.
Exemple de positionnement non valide. La figure suivante montre un positionnement non valide car les deux joueurs avec des chasubles rouges sont à deux extrémités d’une même arête. Pour ce graphe, le joueur avec une chasuble verte doit nécessairement se positionner sur le sommet central.
Comment lire les figures qui vont suivre ? Dans la suite, la couleur de chaque sommet représentera la couleur de la chasuble du joueur positionné sur ce sommet. La solution pour notre exemple est décrite dans la figure suivante.
Lien avec l’allocation de fréquences dans les réseaux sans fil.
Nous expliquons une des applications en lien avec l’allocation de fréquence dans les réseaux de télécommunication sans fil. Dans ce type de réseaux, deux émetteurs trop proches ne peuvent pas émettre sur une fréquence identique. En effet, dans ce cas, il y aurait des interférences et certaines communications ne seraient alors plus effectuées correctement. Dans ce contexte, il faut alors attribuer une fréquence différente pour chacun des deux émetteurs. De plus, il n’est pas envisageable d’avoir un nombre de fréquences égal au nombre d’émetteurs. Il faut donc attribuer une fréquence à chaque émetteur en respectant toutes les contraintes d’interférence pour tous les émetteurs du réseau tout en minimisant le nombre de fréquences différentes pour y parvenir.
Ce problème est modélisé par un problème de coloration de sommets dans un graphe construit à partir du réseau. Il y a un sommet par émetteur et il y a une arête entre deux sommets si et seulement si les deux émetteurs correspondants à ces deux sommets sont trop proches pour utiliser la même fréquence. Le problème revient alors à donner une couleur à chacun des sommets (deux sommets reliés par une arête ont des couleurs différentes) tout en minimisant le nombre total de couleurs utilisées. Les couleurs représentent dans ce contexte les fréquences. Par exemple, si le réseau correspond à notre graphe décrit précédemment, alors le plus petit nombre de couleurs (fréquences) permettant d’obtenir une solution valide est trois.
Graphes pour jouer.
Télécharger tous les graphes pour jouer.
Jeu 1. Le graphe est composé de cinq sommets. Il y a deux joueurs avec une chasuble rouge, deux joueurs avec une chasuble bleue et un joueur avec une chasuble verte.
Jeu 2. Le graphe est composé de dix sommets. Il y a quatre joueurs avec une chasuble rouge, trois joueurs avec une chasuble bleue et trois joueurs avec une chasuble verte.
Jeu 3. Le graphe est composé de dix sommets. Il y a cinq joueurs avec une chasuble rouge et cinq joueurs avec une chasuble bleue.
Jeux 4 à 21. La figure suivante décrit dix-huit jeux de coloration des sommets. La répartition des couleurs des chasubles est représentée par les sommets de couleur situés au dessus de chacun des graphes.
Jeux 22 à 36. La figure suivante décrit quinze jeux de coloration des sommets. La répartition des couleurs des chasubles est représentée par les sommets de couleur situés au dessus de chacun des graphes.
