Polytope des stables
- Polytope des stables
-
Un stable est un ensemble de sommets deux-à-deux non adjacents. Le polytope des stables de G est l'enveloppe convexe des fonctions caractéristiques de ses stables.
Plus précisément, soit G un graphe à n sommets. Un choix de numérotation fait correspondre à chaque sommet de G un vecteur de la base canonique de l'espace euclidien usuel 
. Plus généralement, à toute partie F de l'ensemble des sommets de G correspond le vecteur dont les coordonnées valent 0 ou 1 selon que le sommet correspondant appartient à F ou non. Chaque stable de G definit ainsi un point de , et le polytope des stables d'un graphe est l'enveloppe convexe de ces points.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Polytope des stables de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … 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
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
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
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
