Contraintes de clique
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
En optimisation combinatoire et théorie des graphes, les contraintes de cliques sont des contraintes, au sens de l'optimisation linéaire.
Définition[modifier | modifier le code]
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[modifier | modifier le code]
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.
Bibliographie[modifier | modifier le code]
Notes et références[modifier | modifier le code]
