Neutralité du problème de coloration de graphe

Abstract

Le problème de coloration de graphe (GCP) est un problème d'optimisation combinatoire très étudié dans la littérature. En effet, de nombreux problèmes réels, comme l'allocation de fréquences dans les télécommunications, sont modélisés et résolus via la coloration de graphe. Nous nous intéressons, ici, pour un nombre de couleurs donné k, à minimiser le nombre d'arêtes dont les extrémités sont identiquement coloriées. Ce nombre correspond au nombre de conflits dans la solution. De nombreuses observations font mention de la présence de solutions de même qualité, avec un nombre identique de conflits. Lorsque deux solutions voisines, en terme d'opérateur de voisinage, ont la même qualité, on parle de neutralité. Les recherches locales se déplaçant entre les solutions voisines, cette neutralité représente alors une frontière difficile à franchir. Plusieurs questions se posent alors quant à la quantité de ces solutions de même qualité et à la manière de tirer bénéfice de cette neutralité au cours de la résolution du problème. Dans cette étude, nous commencerons par quantifier et caractériser la neutralité de certaines instances difficiles de la littérature. Puis, nous montrerons que cette neutralité peut être exploitée par le processus de recherche.