Contraintes de clique
En optimisation combinatoire et théorie des graphes, les contraintes de cliques sont des contraintes, au sens de l'optimisation linéaire.
DĂ©finition
Soit G un graphe. On munit l'espace usuel à n dimensions d'une correspondance entre ses dimensions et les sommets de G. À toute clique K de G on peut associer une contrainte linéaire sur un vecteur x de l'espace, appelée contrainte de clique :
- la somme des composantes de x correspondant aux sommets de la clique K doit être inférieure ou égale à 1.
Il découle directement des définitions que tout vecteur 0-1 est caractéristique d'un stable de G si et seulement il satisfait les contraintes de clique (en fait les cliques de taille 2 suffisent).
Que peut-on dire des vecteurs positifs fractionnaires (pas nécessairement entiers) satisfaisant les contraintes de clique, appartiennent-ils au polytope des stables de G ? La réponse est non puisque, si G est un cycle impair (différent du triangle), on obtient un contre-exemple avec le vecteur 1/2.
Lien avec les graphes parfaits
Václav Chvátal a montré que les vecteurs satisfaisant les contraintes de clique sont précisément ceux du polytope si et seulement si G est parfait. En d'autres termes, les hyperplans définis par les contraintes de cliques décrivent alors le polytope.
Notes et références