Les sommets veulent leur indépendance

 

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 déterminé avant le début du jeu. Le jeu est collaboratif : tous les joueurs gagnent ou tous les joueurs perdent. Dans notre exemple, il y a trois joueurs.

But du jeu. Les joueurs doivent se positionner sur les sommets du graphe (deux joueurs ne peuvent pas être sur un même sommet) de telle sorte que chaque sommet ayant un joueur positionné dessus n’ait pas de sommet voisin contenant également un joueur (les sommets voisins d’un sommet représentent tous les sommets qui partagent une arête avec ce sommet). Autrement dit, pour chacune des arêtes, il y a au plus une de ses deux extrémités qui contient un joueur.

Exemple de solution. La figure suivante représente une solution pour notre exemple. Notons que si le nombre de joueurs est quatre, alors il n’y a pas de solution pour ce graphe.

Exemple de positionnement non valide. La figure suivante montre un positionnement non valide car deux joueurs sont aux deux extrémités d’une même arête.

Comment lire les figures qui vont suivre ? Dans la suite, un sommet rouge représentera un sommet avec un joueur positionné dessus. La solution pour notre exemple est décrite dans la figure suivante.

 

Une application pour l’organisation de votre fête.
Vous souhaitez organiser une fête avec vos amis. La difficulté est que certaines personnes ne s’apprécient pas. D’une manière assez simplifiée, nous supposons ici que deux personnes sont amis ou ennemis. Vous voulez inviter le plus grand nombre de personnes possibles à votre fête mais vous ne voulez pas que deux ennemis s’y trouvent. Pour résoudre ce problème, nous construisons un graphe qui va représenter votre réseau. Il y a un sommet par personne et il y a une arête entre deux sommets si les deux personnes correspondantes à ces sommets sont ennemis. Si deux personnes sont amis, alors il n’y a pas d’arête entre les deux sommets correspondants à ces deux personnes. Il faut alors trouver le plus grand nombre de joueurs tel qu’il existe une solution pour le jeu de l’indépendance. Par exemple si votre réseau est le graphe correspondant à notre exemple, vous pourrez inviter trois personnes au maximum (voir solution décrite précédemment).

 

Graphes pour jouer.

Télécharger tous les graphes pour jouer.

Jeu 1. Le graphe est composé de cinq sommets et il y a trois joueurs.

Jeux 2 à 19. La figure suivante décrit dix-huit jeux de l’indépendance. Le nombre de joueurs est indiqué pour chacun des graphes.

Jeux 20 à 34. La figure suivante décrit quinze jeux de l’indépendance. Le nombre de joueurs est indiqué pour chacun des graphes.

Les commentaires sont clos.