Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Topologie combinatoire --- Probleme du coloriage --- Topologie combinatoire --- Probleme du coloriage

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Graphes, Théorie des --- Graphes planaires --- Graph theory. --- Topologie combinatoire --- Probleme du coloriage --- Topologie combinatoire --- Probleme du coloriage

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Contrairement aux jeux dits "partisans", la particularité des jeux combinatoires impartiaux est que les deux joueurs ont des options de jeu identiques. Un des attraits de ces jeux aux règles généralement simples, est que les stratégies gagnantes sont parfois très compliquées à trouver, notamment pour les jeux de coloriage impartiaux. Ce travail s'articule principalement autour de l'article de G. Beaulieu, K. Burke et E. Duchêne, intitulé "Impartial Coloring Games". Il se décompose en huit chapitres.
En guise d’introduction, deux jeux combinatoires impartiaux très célèbres sont étudiés : le jeu des bâtonnets et le jeu de Marienbad. Ceux-ci permettent de présenter au lecteur les notions de stratégie et de position gagnantes ainsi que des démarches permettant d’obtenir une telle stratégie. De par sa simplicité, le jeu des bâtonnets est mis en lien avec un jeu joué sur un graphe, ce qui amène au cœur du sujet : les jeux de coloriage impartiaux.
Afin de pouvoir approfondir notre étude, certains outils théoriques relatifs aux notions de calculabilité et de la théorie de la complexité (machine de Turing, fonction calculable par machine de Turing, espaces PSPACE, problèmes décidables par machine de Turing, …) sont rappelés. 
Ensuite, la fonction de Sprague-Grundy et certaines de ses extensions et applications, ainsi que les notions de mex, de jeu de coloriage successif et de valeur de Grundy d’une position d’un jeu de coloriage successif sont étudiées. La valeur de Grundy est alors étendue aux autres jeux combinatoires impartiaux par le biais du graphe des positions d’un jeu acyclique.
Enfin, lorsque le graphe sur lequel se déroule la partie est non connexe, il est naturel de considérer que l’on joue simultanément à plusieurs jeux de coloriage indépendants, sur des graphes connexes. Ceci mène à la notion de somme de jeux, à l’introduction de la somme de Nim et à un résultat très important en théorie des jeux combinatoires : le théorème de Sprague-Grundy. 
Les définitions et résultats obtenus précédemment sont alors appliqués à divers jeux de coloriage impartiaux tels que les k-coloriages propres, coloriages orientés, faibles, 2-distants et séquentiels. Entre autres, pour les jeux précités, il est montré que déterminer si une position de ces jeux est gagnante est un problème PSPACE-complet.

Jeux --- Sprague-Grundy --- Coloriage --- Graphe --- Stratégie --- Physique, chimie, mathématiques & sciences de la terre > Mathématiques

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Discrete mathematics --- 51 <082.1> --- Mathematics--Series --- Graph coloring --- Ramsey theory --- Random graphs. --- Coloriage de graphes --- Ramsey, Théorie de --- Graphes aléatoires --- Random graphs --- Coloring of graphs --- Graph theory --- Graphs, Random --- Combinatorial analysis --- Coloriage de graphes. --- Ramsey, Théorie de. --- Graphes aléatoires.

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Une branche centrale de la théorie des graphes est le coloriage propre des sommets d'un graphe, qui consiste à attribuer des couleurs distinctes à des sommets adjacents. Ce mémoire vise à analyser le nombre chromatique de diverses familles de graphes classiques et à examiner les bornes de ce nombre. En outre, ce travail explore le concept de polynôme chromatique ainsi que les notions d'équivalence chromatique et d'unicité chromatique. Pour terminer, la complexité algorithmique du problème de coloriage des sommets est étudiée.

Mathématiques --- Théorie des graphes --- Coloriage propre --- Nombre chromatique --- Polynôme chromatique --- Physique, chimie, mathématiques & sciences de la terre > Mathématiques