Exposé n° 75 : La théorie des graphes dans toutes ses couleurs

La théorie des graphes trouve ses origines dans la résolution du problème des sept ponts de Königsberg proposée par le célèbre mathématicien Leonhard Euler (1707-1783). C’est aujourd’hui une discipline mathématique et informatique qui permet de résoudre de très nombreux problèmes. Dans cet exposé, nous partirons de trois problèmes concrets comme la résolution de grilles de sudoku, la conception d’horaires de cours ou encore l’allocation de fréquences dans les réseaux GSM. Nous montrerons comment on peut modéliser les situations observées par des graphes et comment la coloration de ces graphes permet de résoudre les problèmes soulevés. Lors de cet exposé, nous expliquerons aussi comment on peut concevoir un programme informatique permettant de colorer un graphe et donc de résoudre les trois problèmes étudiés.

Exposé proposé par Véronique Bruyère.