la demi-journée de la Régionale le mercredi 18 Décembre 2024 à 14h qui se déroulera en deux parties :
- 14h-15h : Coloration de graphes. Conférence tout public de Vincent Picard (docteur et professeur d’informatique en CPGE MPI).
Résumé :
Colorer un graphe consiste à donner une couleur à chacun de ses sommets de telle sorte à ce que deux sommets adjacents n’aient pas la même couleur. La coloration de graphes possède de nombreuses applications pratiques : algorithmes de planification (emplois du temps, taxis), ordonnancement de tâches, écriture des compilateurs, résolutions de contraintes (Sudoku,…).
Cependant, savoir si un graphe possède une coloration n’utilisant que k couleurs est un problème algorithmiquement difficile pour k > 2, démontré NP-complet en 1972. Plusieurs théorèmes célèbres concernant la coloration de graphes n’ont été démontrés qu’assez récemment : théorème des 4 couleurs (1976, 2005), théorème des graphes parfaits (2006).
Dans cet exposé, on présente le problème de la coloration de graphes et on étudie un algorithme glouton de coloration. On montre pour certaines classes de graphes (graphes d’intervalles, graphes cordaux) que cet algorithme permet de colorer un graphe avec un nombre minimal de couleurs.
15h-16h : Assemblée générale de la Régionale APMEP Réunion.
Nous vous souhaitons de très bonnes fêtes de fin d’année et de belles aventures mathématiques,