Les Jeux-graphes

Résumé: Un jeu combinatoire est un jeu à deux joueurs, fini, sans intervention de la chance et sans informations cachées. Les joueurs jouent chacun son tour, selon des règles bien précises, et en convention normale, le premier qui ne peut plus jouer perd la partie. Un jeu à objectif compétitif sur un graphe est un jeu combinatoire dont les règles et les conditions de victoire sont reliées à un problème d'optimisation/un invariant du graphe. De nombreux jeux ont ainsi été définis permettant d'introduire de nouveaux invariants, souvent appelés invariants ludiques et de les étudier. Dans cet exposé, nous rappelons les éléments essentiels de la théorie de la complexité algorithmique permettant d'étudier ces invariants et donnerons les résultats les plus récents relatifs à quelques-uns des invariants les plus étudiés.

Publié dans la revue: Séminaire Mathématique de Béjaia