Groupe d’études et de recherche en analyse des décisions

Une vision colorée de la théorie des graphes

Alain Hertz Professeur titulaire, Département de mathématiques et de génie industriel, Polytechnique Montréal, Canada

Étant donné un graphe \(G\) avec un ensemble \(V\) de sommets et un ensemble \(E\) d’arêtes, on peut s’intéresser à colorer ses sommets et/ou ses arêtes. Lorsqu’on colore les sommets, on impose la contrainte que les extrémités de chaque arête doivent être de couleur différente, et lorsqu’on colore les arêtes, on impose la contrainte qu’aucun sommet ne doit avoir plusieurs arêtes de même couleur qui lui sont incidentes.

Les applications de la coloration de graphes sont nombreuses et variées. De manière abstraite, on doit déterminer une partition d’un ensemble d’objets conflictuels. Chaque bloc de la partition doit contenir des objets non conflictuels Si les objets sont représentés par des sommets, chaque conflit entre deux objets donne lieu à une arête entre les sommets correspondants. Si par contre les objets sont représentés par des arêtes, on impose que deux arêtes correspondant à deux objets conflictuels aient une extrémité en commun.

La coloration de graphes constitue donc un modèle naturel pour la confection d’horaires, les tâches à planifier correspondant aux objets et les blocs de la partition aux périodes de l’horaire. Il y a conflit entre deux tâches lorsque celles-ci ne peuvent pas être planifiées simultanément. D’autres exemples d’applications de la coloration de graphes sont par exemple l’affectation de fréquences en télécommunication, l’entreposage de denrées dangereuses, ou la recomposition des trains dans les gares. Certaines de ces applications nécessitent une extension des modèles de base de la coloration de graphes. On peut par exemple considérer des colorations « pondérées », des colorations « cycliques », ou des colorations « par listes ». Le but de cette présentation est de passer en revue les modèles de base et les extensions des problèmes de colorations.