title: Contraintes de clique
text: # 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.
  
  