Séminaire Mathématique de Béjaia
Volume 16, Numéro 1, Pages 25-25
2018-12-31
Les Jeux-graphes
Auteurs : Aider Méziane .
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.
Mots clés
Jeux, Graphes, Complexité algorithmique.
Les articles similaires
Ferhat Arezki
.
Radjef Mohammed Said
.
pages 3-5.
Yalaoui Bilal
.
pages 224-240.
Kabyl Kamel
.
Berrachedi Abdelhafid
.
pages 25-28.
Muller Manfred
.
pages 78-96.
Nabi Mohamed Nadjeh
.
Belafrites Yacine
.
Hamlaoui Ameur
.
pages 849-862.
