Abstract - meunier (original) (raw)
S�minaire du 25 septembre 06, Fr�d�ric Meunier, Projet Algorithmes.
Sigma-jeux sur la grille
Supposons donn� un graphe dont les sommets peuvent prendre deux �tats, allum� ou �teint, et tel que, lorsqu'on appuie sur un sommet v, l'�tat des voisins de v change. Le jeu est alors le suivant : partant du graphe dont tous les sommets sont �teints, appuyer sur des sommets afin d'allumer tous les sommets du graphe. Dans quels cas peut-on y parvenir ? Et s'il est possible d'y parvenir, comment trouver la s�quence d'appuis gagnante ? Nous nous int�resserons en particulier au cas de la grille et pr�senterons la d�monstration d'une conjecture parue en 2002 dans la revue Pour la Science.
Last modified: Mon May 23 18:32:54 CEST 2005