Contraintes De Clique
- Contraintes De Clique
-
Contraintes de clique
Soit G un graphe. On munit l'espace usuel à n dimensions d'une correspondance entre ses dimensions et les sommets de G. A 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.
Chvatal 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.
Portail des mathématiques
Catégories : Concept en théorie des graphes | Optimisation combinatoire
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Contraintes De Clique de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Contraintes de clique — Soit G un graphe. On munit l espace usuel à n dimensions d une correspondance entre ses dimensions et les sommets de G. A toute clique K de G on peut associer une contrainte linéaire sur un vecteur x de l espace, appelée contrainte de… … Wikipédia en Français
Graphe parfait — Théorème des graphes parfaits Sommaire 1 Contexte 2 Théorèmes 3 Intérêt 4 Notes 5 Références … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Theoreme des graphes parfaits — Théorème des graphes parfaits Sommaire 1 Contexte 2 Théorèmes 3 Intérêt 4 Notes 5 Références … Wikipédia en Français
Théorème des graphes parfaits — Le graphe parfait est une notion introduite par Claude Berge, dont les conjectures ont été démontrées en 1972 et 2002 et sont devenues des théorèmes. Sommaire 1 Contexte 2 Théorèmes 3 Intérêt … Wikipédia en Français
Biparti — Graphe biparti Exemple de graphe biparti quelconque En théorie des graphes, un graphe est dit biparti s il existe une partition de son ensemble de sommets en deux sous ensembles U et V telle que chaque arête ait une extrémité dans U et l autre da … Wikipédia en Français
Bipartite — Graphe biparti Exemple de graphe biparti quelconque En théorie des graphes, un graphe est dit biparti s il existe une partition de son ensemble de sommets en deux sous ensembles U et V telle que chaque arête ait une extrémité dans U et l autre da … Wikipédia en Français
Graphe Biparti — Exemple de graphe biparti quelconque En théorie des graphes, un graphe est dit biparti s il existe une partition de son ensemble de sommets en deux sous ensembles U et V telle que chaque arête ait une extrémité dans U et l autre da … Wikipédia en Français
Graphe biparti — Exemple de graphe biparti quelconque En théorie des graphes, un graphe est dit biparti s il existe une partition de son ensemble de sommets en deux sous ensembles U et V telle que chaque arête ait une extrémité dans U et l autre dans … Wikipédia en Français
Graphe bipartite — Graphe biparti Exemple de graphe biparti quelconque En théorie des graphes, un graphe est dit biparti s il existe une partition de son ensemble de sommets en deux sous ensembles U et V telle que chaque arête ait une extrémité dans U et l autre da … Wikipédia en Français
