| Résumé | Le jeu de domination est un jeu à deux joueurs qui jouent alternativement sur un graphe non orienté G. À chaque tour, un joueur supprime un sommet ainsi que l'ensemble de ses voisins. En version 'normale', le joueur qui supprime le dernier sommet gagne la partie. En version 'misère', le joueur qui supprime le dernier sommet perd la partie. L'étude d'un tel jeu consiste d'une part à déterminer si une position de jeu est gagnante ou perdante pour le joueur qui doit jouer, et d'autre part à définir la stratégie gagnante (lorsque la position est gagnante).
Lorsque le graphe G est non connexe, le jeu peut être vu comme une 'composition' des jeux sur chaque composante connexe. Le jeu de domination, tel que nous l'avons décrit, correspond à la 'somme disjonctive' des jeux sur les composantes connexes : un joueur choisit l'une des composantes, puis supprime un sommet et ses voisins dans cette composante.
Dans son livre "On Numbers and Games", H. J. Conway a proposé 12 façons de jouer sur des compositions de jeux combinatoires. Nous présenterons ces 12 versions et, dans le cas du jeu de domination sur des chemins, résoudrons 10 de ces 12 versions.
|