|
|
|
Intitulé:
Le jeu de Timber du groupe GT Graphes et Applications
|
Date | 2012-10-19 14:00-15:00 |
Titre | Le jeu de Timber |
Résumé | Nous proposons une variante impartiale du jeu Toppling dominoes, Timber. Le jeu se joue sur un graphe orienté. Deux joueurs choisissent à tour de rôle un arc du graphe. Lorsqu'un arc (x,y) est choisi, il est retiré du jeu ainsi que la composante connexe contenant y dans le graphe non-orienté sous-jacent (ne contenant plus l'arête (x,y)). En version normale, le premier joueur ne pouvant jouer (car il n'y a plus d'arc) perd la partie. En version misère, ce même joueur gagne la partie. Un graphe est perdant (pour le premier joueur) si le second joueur dispose d'une stratégie gagnante.
Nous caractérisons les graphes connexes perdants en version normale, et les chemins perdants en version misère. Nous remarquons par ailleurs que le nombre de chemins perdants de longueur paire en version normale est donné par les nombres de Catalan. |
Lieu | Amphi du LaBRI |
Orateur | Gabriel Renault |
Url | Labri, Univ. de Bordeaux - CNRS |
Aucun document lié à cet événement. RetourRetour à l'index
| |