Il faut casser tous les cycles

 

Règles du jeu et exemple.

Nous définissons tout d’abord la notion de cycle, qui est centrale pour ce jeu.

Qu’est-ce qu’un cycle ? Un cycle est un chemin tel que le premier sommet et le dernier sommet sont reliés par une arête. Un chemin est une suite de sommets telle que deux sommets consécutifs dans cette liste sont nécessairement reliés par une arête. Par exemple, la suite de sommets b, c, f est un cycle du graphe décrit ci-dessous, car c’est un chemin et le sommet f et le sommet b sont reliés par une arête. Autre exemple, la suite de sommets c, d, h, g forme également un cycle dans le graphe.

Graphe. Le jeu se déroule avec un graphe quelconque. Considérons par exemple le graphe suivant composé de neuf 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 deux 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 cycle du graphe contienne au moins un sommet avec un joueur positionné dessus. Autrement dit, les joueurs doivent casser tous les cycles.

Exemple de solution. La figure suivante représente une solution pour notre exemple. Tous les cycles du graphe passent par au moins un sommet avec un joueur positionné dessus. Notons qu’il n’y a pas de solution s’il n’y a qu’un joueur.

De manière équivalente, si tous les sommets avec un joueur positionné dessus sont supprimés, alors le graphe ne contient plus de cycle.

Exemple de positionnement non valide. Dans la figure suivante, il y a un cycle (arêtes rouges) qui ne contient aucun joueur.

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.

 

Graphes pour jouer.

Télécharger tous les graphes pour jouer.

Jeu 1. Le graphe est composé de neuf sommets et il y a deux joueurs.

Jeux 2 à 19. La figure suivante décrit dix-huit jeux des cycles et des solutions. Le nombre de joueurs est indiqué pour chacun des graphes.

Jeux 20 à 34. La figure suivante décrit quinze jeux des cycles et des solutions. Le nombre de joueurs est indiqué pour chacun des graphes.

 

 

Les commentaires sont clos.